基于二維元胞自動(dòng)機(jī)的網(wǎng)絡(luò)模型

摘 要:針對(duì)一維元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型的轉(zhuǎn)發(fā)過(guò)程隨機(jī)化，二維模型缺乏擁塞特性分析的缺陷，提出了一種基于二維元胞自動(dòng)機(jī)的網(wǎng)絡(luò)模型。根據(jù)TCP/IP擁塞控制協(xié)議設(shè)計(jì)了元胞更新規(guī)則，并設(shè)置不同的元胞隊(duì)列長(zhǎng)度以增強(qiáng)網(wǎng)絡(luò)的異構(gòu)性。利用該模型仿真得到了擁塞相態(tài)下的節(jié)點(diǎn)負(fù)載、節(jié)點(diǎn)處理延時(shí)具有白噪聲特性和1/f噪聲特性。通過(guò)該模型觀測(cè)到局部網(wǎng)絡(luò)與整個(gè)網(wǎng)絡(luò)負(fù)載特性的關(guān)系，表明該二維元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型具有可擴(kuò)展性，適用于大規(guī)模網(wǎng)絡(luò)的行為建模研究。

關(guān)鍵詞:擁塞; 元胞自動(dòng)機(jī); 負(fù)載; 延時(shí)

中圖分類號(hào):TP393

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)02-0614-04

doi:10.3969/j.issn.1001-3695.2010.02.059

Network model based on two-dimensional cellular automation

LIU Jia1， ZHANG Wen-zhu2， JIN De-peng2， YUAN Jian2， ZENG Lie-guang2， WANG Yao-xi3

(1.China Mobile Group Pesign Institute Co. Ltd， Beijing 100080， China; 2.Dept. of Electronic Engineering， Tsinghua University， Beijing 100084， China; 3.Yunnan Computer Center， Yunnan University， Kunming 650223， China)

Abstract:Aiming to improve the shortcomings such as random forwarding and lacking analysis of congestion in one-dimensional and two-dimensional cellular automation model， this paper proposed a network model based on the two-dimensional cellular automaton. The transition rule of cells was designed in accordance with TCP/IP congestion control protocol， and the cellular in the model was with different queue length in order to enhance the heterogeneity of the network. The simulation results reveal that the traffic load of the node and the processing delay of the node are with characters of white noise and 1/f noise. The difference of the load characteristics between the local networks and the entire networks is also observed. It is shows that the model based on the two-dimensional cellular automaton is scalable and applicable for research on the behavior of large-scale networks.

Key words:congestion; cellular automation; load; delay

0 引言

由于網(wǎng)絡(luò)結(jié)構(gòu)越來(lái)越復(fù)雜，研究者對(duì)真實(shí)的網(wǎng)絡(luò)進(jìn)行各種建模，以方便研究其內(nèi)部的一些特性，如隨機(jī)圖模型[1]、小世界模型[2]等都是比較典型的網(wǎng)絡(luò)模型。網(wǎng)絡(luò)建模在網(wǎng)絡(luò)技術(shù)的研究中有著重要的意義，是網(wǎng)絡(luò)性能研究不可缺少的工具。元胞自動(dòng)機(jī)以其結(jié)構(gòu)簡(jiǎn)單、易于擴(kuò)展、非常適合計(jì)算機(jī)仿真等諸多優(yōu)點(diǎn)獲得了網(wǎng)絡(luò)建模研究者的青睞。一維元胞自動(dòng)機(jī)理論成熟，模型簡(jiǎn)單，目前在網(wǎng)絡(luò)建模方面應(yīng)用比較廣[3～5]，但是一維元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型將節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包過(guò)程隨機(jī)化，缺乏擁塞控制過(guò)程，與實(shí)際網(wǎng)絡(luò)偏差較大，而且由于維度限制不利于大規(guī)模網(wǎng)絡(luò)特性的研究。Jian等人[6]提出了一種基于二維元胞自動(dòng)機(jī)的網(wǎng)絡(luò)模型，在模型中加入了擁塞控制協(xié)議，但是模型的每個(gè)元胞緩沖區(qū)排隊(duì)長(zhǎng)度設(shè)置為無(wú)限長(zhǎng)，因此擁塞控制協(xié)議并未起到擁塞控制的作用，只能對(duì)自由相態(tài)下的網(wǎng)絡(luò)特性進(jìn)行模擬。實(shí)際的網(wǎng)絡(luò)是異構(gòu)的，存在著瓶頸節(jié)點(diǎn)，擁塞是其固有屬性，因此對(duì)擁塞相態(tài)下網(wǎng)絡(luò)特性的研究是非常重要的。

針對(duì)現(xiàn)有研究的不足，本文提出了基于TCP/IP協(xié)議的異構(gòu)二維元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型，對(duì)擁塞相態(tài)下的網(wǎng)絡(luò)特性作了研究，并分析了網(wǎng)絡(luò)局部負(fù)載特性和全網(wǎng)負(fù)載特性的關(guān)系，為大規(guī)模網(wǎng)絡(luò)的研究提供了新的思路。

1 元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)是一種時(shí)空離散的局部動(dòng)力學(xué)模型，是對(duì)結(jié)構(gòu)復(fù)雜的系統(tǒng)研究的一個(gè)典型方法，特別適合用于空間復(fù)雜系統(tǒng)的時(shí)空動(dòng)態(tài)模擬研究。

1.1 元胞自動(dòng)機(jī)的概念

元胞自動(dòng)機(jī)是由空間上各向同性的一系列元胞組成，用于模擬和分析幾何空間內(nèi)的各種現(xiàn)象。標(biāo)準(zhǔn)的元胞自動(dòng)機(jī)是一個(gè)四元組:A=(Ld， S， N， f)。其中:A代表一個(gè)元胞自動(dòng)機(jī)系統(tǒng);L表示元胞空間，d是一個(gè)正整數(shù)，表示元胞自動(dòng)機(jī)內(nèi)元胞空間的維數(shù);S是元胞有限的、離散的狀態(tài)集合;N表示一個(gè)所有鄰居內(nèi)元胞的組合(包括中心元胞)，即包含n個(gè)不同元胞狀態(tài)的一個(gè)空間矢量，記為N=(s1， s2， …， sn)，n是元胞的鄰居個(gè)數(shù)。

1.2 二維元胞自動(dòng)機(jī)

對(duì)于最常見的二維元胞自動(dòng)機(jī)，二維元胞空間通常可以按照三角形、正方形或六邊形等網(wǎng)格排列，如圖1所示。這三種規(guī)則的元胞空間劃分在模型構(gòu)建時(shí)各有優(yōu)缺點(diǎn):a)三角網(wǎng)格的優(yōu)點(diǎn)是擁有相對(duì)較少的相鄰元胞數(shù)目，并且易于處理復(fù)雜邊界;其缺點(diǎn)是計(jì)算機(jī)的表達(dá)與顯示不方便，需要轉(zhuǎn)換為四方形網(wǎng)格;b)正方形網(wǎng)格的優(yōu)點(diǎn)是直觀而簡(jiǎn)單，而且特別適合于現(xiàn)有計(jì)算機(jī)環(huán)境下進(jìn)行表達(dá)顯示;其缺點(diǎn)是不能較好地模擬各向同性現(xiàn)象;c)六邊形網(wǎng)格的優(yōu)點(diǎn)是能較好地模擬各向同性的現(xiàn)象;其缺點(diǎn)同三角模型一樣，在表達(dá)顯示上較為困難。

應(yīng)用中一般采用正方形網(wǎng)格的二維模型。其鄰居通常有三種表達(dá)形式，如圖2所示，黑色元胞為中心元胞，灰色元胞為其鄰居，它們的狀態(tài)一起決定中心元胞在下一時(shí)刻的狀態(tài)。

在二維元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型中，鄰居范圍的不同決定了數(shù)據(jù)包轉(zhuǎn)發(fā)的路徑選擇。為了方便起見，本文選取了Von.Neumann型的元胞自動(dòng)機(jī)作為網(wǎng)絡(luò)原型。

2 基于二維元胞自動(dòng)機(jī)的網(wǎng)絡(luò)模型

根據(jù)第1章的介紹可知，元胞自動(dòng)機(jī)是由最基本的四部分組成，即元胞、元胞空間、鄰居及規(guī)則。下面就依照這四部分來(lái)介紹本文提出的網(wǎng)絡(luò)模型。

2.1 元胞

模型采用單一節(jié)點(diǎn)元胞，每個(gè)元胞代表一個(gè)路由器節(jié)點(diǎn)。每個(gè)路由器在不同時(shí)刻緩存數(shù)據(jù)包的個(gè)數(shù)代表了元胞的狀態(tài)，如圖3所示。在本模型中，假設(shè)二維元胞自動(dòng)機(jī)模型規(guī)模為N=L×L(N為元胞自動(dòng)機(jī)中總的節(jié)點(diǎn)數(shù)，L為二維元胞自動(dòng)機(jī)格子圖的長(zhǎng)度)，第i(i=1，2，…，N)個(gè)節(jié)點(diǎn)的緩存區(qū)存儲(chǔ)量為Bi，則元胞的狀態(tài)空間為S={0，1，2，…，maxBi}。

2.2 元胞空間

二維元胞自動(dòng)機(jī)的元胞空間就是一個(gè)二維格子空間，其邊界分為封閉式邊界和開放式邊界兩種。在封閉式邊界的元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型中的數(shù)據(jù)包不會(huì)在邊界出現(xiàn)或者消失，而是在這些元胞內(nèi)循環(huán)前進(jìn)。而開放式邊界的元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型中，所有的數(shù)據(jù)包能夠“進(jìn)”“出”它的邊界。元胞自動(dòng)機(jī)模型中已經(jīng)證實(shí)封閉式和開放式模型并沒(méi)有什么明顯的差異，這是因?yàn)椴煌倪吔绱藭r(shí)影響的只是路由計(jì)算上的距離[7]。為了與Jian等人的二維模型進(jìn)行比較，本文的模型選取了周期邊界的形式。

2.3 鄰居

本文采用了Von.Neumann型二維元胞自動(dòng)機(jī)。每個(gè)元胞有上、下、左、右四個(gè)鄰居，如圖2(a)所示。元胞在元胞空間中的位置可采用笛卡爾單位矢量表示為r=icx+jcy。其中:cx和cy為笛卡爾矢量。因此，中心元胞的鄰居可以表示為{r-cx，r+cx，r-cy，r+cy}。

2.4 更新規(guī)則

網(wǎng)絡(luò)協(xié)議規(guī)定了網(wǎng)絡(luò)中節(jié)點(diǎn)自身工作的方式以及節(jié)點(diǎn)之間通信的方式，因而映射到元胞自動(dòng)機(jī)中對(duì)應(yīng)元胞的更新規(guī)則。為了更好地模擬網(wǎng)絡(luò)，在模型中引入了TCP/IP擁塞控制協(xié)議，主要包括慢啟動(dòng)、擁塞回避、快速重傳和快速恢復(fù)四個(gè)過(guò)程。慢啟動(dòng)和擁塞回退原則主要是在網(wǎng)絡(luò)非擁塞情況下采取的控制措施。因?yàn)槟Ｐ椭性O(shè)定每個(gè)路由器的緩沖區(qū)是有限的(Bi)，所以網(wǎng)絡(luò)中可能出現(xiàn)擁塞現(xiàn)象。TCP/IP的擁塞控制協(xié)議認(rèn)為擁塞的主要依據(jù)為是否發(fā)生了數(shù)據(jù)包的重傳。網(wǎng)絡(luò)中，TCP對(duì)每一個(gè)包都有一個(gè)定時(shí)器，稱為重傳定時(shí)器(RTO)，當(dāng)RTO超時(shí)且還沒(méi)有得到數(shù)據(jù)確認(rèn)，那么TCP就會(huì)對(duì)該報(bào)文段進(jìn)行重傳。當(dāng)發(fā)生超時(shí)，那么出現(xiàn)擁塞的可能性就很大，某個(gè)數(shù)據(jù)包可能在網(wǎng)絡(luò)中某處丟失，并且后續(xù)的數(shù)據(jù)包也沒(méi)有了消息，在這種情況下，TCP就判斷發(fā)生了擁塞，并且通過(guò)快速重傳、快速恢復(fù)進(jìn)行控制。圖4中描述了TCP/IP擁塞控制協(xié)議下數(shù)據(jù)窗的調(diào)整過(guò)程，cwnd表示窗口大小，ssthresh表示慢啟動(dòng)閾值。

模型中的每個(gè)元胞相當(dāng)于是一個(gè)路由器節(jié)點(diǎn)，其下面都會(huì)有終端，即數(shù)據(jù)源。這里數(shù)據(jù)源采用ON/OFF模型。因此元胞的功能結(jié)合了路由器和數(shù)據(jù)源的功能，進(jìn)行數(shù)據(jù)包的發(fā)送、接收和轉(zhuǎn)發(fā)。模型中節(jié)點(diǎn)狀態(tài)在發(fā)送數(shù)據(jù)包時(shí)的更新流程如圖5所示，圖中左邊方框代表了發(fā)包控制器的工作流程，右邊框代表了擁塞控制協(xié)議下發(fā)送速率的調(diào)整。發(fā)送包過(guò)程其實(shí)是數(shù)據(jù)源的數(shù)據(jù)包注入網(wǎng)絡(luò)的過(guò)程，主要由發(fā)包計(jì)數(shù)器控制、數(shù)據(jù)包個(gè)數(shù)服從Pareto分布，發(fā)包計(jì)數(shù)器根據(jù)發(fā)包進(jìn)行減計(jì)數(shù)，每次減計(jì)數(shù)到0時(shí)則數(shù)據(jù)源由ON/OFF狀態(tài)進(jìn)入OFF/ON狀態(tài)。速率調(diào)整部分主要是根據(jù)ACK的到達(dá)超時(shí)與否來(lái)進(jìn)行數(shù)據(jù)窗的調(diào)整，進(jìn)而調(diào)整發(fā)送速率。

圖6描述了模型中數(shù)據(jù)包的接收和轉(zhuǎn)發(fā)流程。當(dāng)節(jié)點(diǎn)收到數(shù)據(jù)包時(shí)，先判斷接收地址是否為本地地址，如果接收地址為本地地址則進(jìn)入接收過(guò)程，否則進(jìn)入轉(zhuǎn)發(fā)過(guò)程。接收過(guò)程又分兩種情況:如果接收的數(shù)據(jù)包是ACK數(shù)據(jù)包，則需要計(jì)算RTT時(shí)間，并且調(diào)整數(shù)據(jù)窗口發(fā)送下一個(gè)數(shù)據(jù)包;如果不是ACK數(shù)據(jù)包，則需要回發(fā)一個(gè)ACK確認(rèn)數(shù)據(jù)包。轉(zhuǎn)發(fā)過(guò)程主要包含了數(shù)據(jù)包的路由計(jì)算、根據(jù)最短路徑計(jì)算數(shù)據(jù)包的下一跳位置。根據(jù)2.3節(jié)的介紹，假設(shè)在周期邊界的元胞自動(dòng)機(jī)中的兩個(gè)元胞位置分別為r1=(i1， j1)，r2=(i2， j2)，則它們之間的距離可按下式計(jì)算:

d(r1， r2)=L-||i1-i2|-L/2|-||j1-j2|-L/2|

路由的目的就是數(shù)據(jù)包在源端和目的端之間的傳遞尋找一條距離最短(或延時(shí)最少)路徑。本模型采用距離最短原則，數(shù)據(jù)包每次要選擇下一跳時(shí)都要計(jì)算四個(gè)鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離。如果存在一個(gè)鄰居與目的節(jié)點(diǎn)存在最短距離且惟一，則選擇次鄰居為下一跳;否則，就以均等概率選取下一跳。

上述過(guò)程即為元胞節(jié)點(diǎn)在TCP/IP的擁塞控制協(xié)議下收發(fā)以及轉(zhuǎn)發(fā)數(shù)據(jù)包的流程。每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)隊(duì)列代表元胞的狀態(tài)。假設(shè)系統(tǒng)有一個(gè)時(shí)鐘，每一個(gè)時(shí)間周期內(nèi)，元胞都要更新自己的隊(duì)列長(zhǎng)度(狀態(tài))。那么根據(jù)TCP/IP協(xié)議的擁塞控制原理，可以得到在一個(gè)時(shí)鐘周期內(nèi)元胞狀態(tài)的更新規(guī)則如下:

a)初始化。記第(i， j)個(gè)元胞，在t時(shí)刻，緩存隊(duì)列長(zhǎng)度表示為nt(i， j)，則對(duì)于每一個(gè)元胞，初始化即有n0(i， j)=0。

b)發(fā)送/轉(zhuǎn)發(fā)過(guò)程。設(shè)(i′，j′)為(i， j)的下一跳元胞，即(i′=i+1， j′=j)，(i′=i-1， j′=j)，(i′=i， j′=j+1)，(i′=i， j′=j-1)四種組合。如果滿足nt(i， j)+1< B(i′，j′)，則nt+1(i， j)= nt(i， j)-1;否則nt+1(i， j)= nt(i， j)。

c)接收過(guò)程。設(shè)B(i， j)為第(i， j)個(gè)元胞的緩沖區(qū)最大長(zhǎng)度，如果nt(i， j)+1< B(i， j)，則nt+1(i， j)= nt(i， j)+1;否則nt(i， j)= B(i， j)。

3 仿真結(jié)果

為了能夠?qū)砣麘B(tài)下的網(wǎng)絡(luò)特性進(jìn)行研究，對(duì)元胞節(jié)點(diǎn)設(shè)置緩沖區(qū)的上限值。同時(shí)，在網(wǎng)絡(luò)中設(shè)置了一些處理能力較低即緩沖區(qū)容量小的節(jié)點(diǎn)作為網(wǎng)絡(luò)的瓶頸節(jié)點(diǎn)，這樣更加接近真實(shí)網(wǎng)絡(luò)的異構(gòu)性。而且在網(wǎng)絡(luò)注入流量超過(guò)節(jié)點(diǎn)緩沖區(qū)上限值時(shí)，網(wǎng)絡(luò)即可進(jìn)入擁塞狀態(tài)。

下面就分別介紹一下網(wǎng)絡(luò)處于擁塞狀態(tài)下，節(jié)點(diǎn)平均負(fù)載分布、節(jié)點(diǎn)處理延時(shí)和局部網(wǎng)絡(luò)與整個(gè)網(wǎng)絡(luò)負(fù)載關(guān)系的仿真結(jié)果。

3.1 節(jié)點(diǎn)負(fù)載分布特性

設(shè)模型的規(guī)模為L(zhǎng)=8，采樣周期為T=15個(gè)步長(zhǎng)，采樣次數(shù)為10 000次，因此相當(dāng)于采集時(shí)間為150 000個(gè)時(shí)間步長(zhǎng)。對(duì)節(jié)點(diǎn)的緩沖區(qū)設(shè)置如下:(4，7)節(jié)點(diǎn)的緩沖區(qū)長(zhǎng)度為例，而對(duì)于除了(4，7)以外的其他節(jié)點(diǎn)，均有B(i， j)=20。為了與Jian等人的結(jié)果對(duì)比，設(shè)置了與其研究中相同的節(jié)點(diǎn)流量強(qiáng)度(λON=10，λOFF=50)。

首先模擬自由流狀態(tài)下的網(wǎng)絡(luò)，即對(duì)每個(gè)元胞節(jié)點(diǎn)的緩沖不作限制。以(4，7)節(jié)點(diǎn)為例，根據(jù)采集到的數(shù)據(jù)對(duì)網(wǎng)絡(luò)的節(jié)點(diǎn)平均排隊(duì)長(zhǎng)度進(jìn)行分析。利用周期圖法對(duì)這組數(shù)據(jù)進(jìn)行功率譜計(jì)算，仿真結(jié)果如圖7(a)所示，節(jié)點(diǎn)(4，7)平均負(fù)載的功率譜具有1/f噪聲特性，斜率約為0.7。可以看到，這個(gè)模擬結(jié)果與Jian等人的結(jié)論一致，即在網(wǎng)絡(luò)中的節(jié)點(diǎn)平均排隊(duì)長(zhǎng)度具有1/f噪聲特性。根據(jù)1/f噪聲特性的性質(zhì)[8]可知，在自由流狀態(tài)下，網(wǎng)絡(luò)中的節(jié)點(diǎn)負(fù)載具有自相似特性。

對(duì)擁塞態(tài)下的網(wǎng)絡(luò)重新分析了節(jié)點(diǎn)(4，7)的負(fù)載特性，仿真結(jié)果如圖7(b)所示。與圖7(a)相比較可以看到，在負(fù)載功率譜的高頻段出現(xiàn)了白噪聲特性。在文獻(xiàn)[4]中，利用一維元胞自動(dòng)機(jī)模型進(jìn)行分析時(shí)，發(fā)現(xiàn)網(wǎng)絡(luò)在擁塞態(tài)下，流量功率譜呈現(xiàn)白噪聲特性。在本模型中，流量功率譜整體呈現(xiàn)1/f噪聲特性，斜率約為0.62，但是隨著網(wǎng)絡(luò)擁塞的加重，1/f噪聲特性減弱。這是因?yàn)樽⑷肽Ｐ偷钠骄髁繌?qiáng)度為λON=10，使網(wǎng)絡(luò)中局部出現(xiàn)了擁塞而造成的。

另外，利用二維元胞自動(dòng)機(jī)模型能夠很方便地觀測(cè)到隨著網(wǎng)絡(luò)負(fù)載的變化，網(wǎng)絡(luò)節(jié)點(diǎn)的擁塞狀況。對(duì)每個(gè)節(jié)點(diǎn)設(shè)置安全水線，一旦超過(guò)水線，就設(shè)定此節(jié)點(diǎn)擁塞狀態(tài)為1，否則為0。利用image函數(shù)對(duì)元胞節(jié)點(diǎn)的擁塞狀態(tài)進(jìn)行了觀測(cè)，如圖8，黑色的點(diǎn)代表?yè)砣脑咨狞c(diǎn)代表工作狀況良好的元胞。圖8(a)～(d)分別代表了時(shí)間t=50，1 000，5 000，6 000的情況下，網(wǎng)絡(luò)節(jié)點(diǎn)的擁塞狀況，通過(guò)仿真結(jié)果能夠直觀地觀測(cè)到哪個(gè)節(jié)點(diǎn)發(fā)生了擁塞，并且可以分析得到隨著網(wǎng)絡(luò)運(yùn)行時(shí)間的加長(zhǎng)，網(wǎng)絡(luò)中存在的瓶頸最終會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)性能的逐漸下降。

3.2 節(jié)點(diǎn)處理延時(shí)特性

Jian等人并未對(duì)節(jié)點(diǎn)的處理延時(shí)進(jìn)行分析。本文針對(duì)擁塞態(tài)下節(jié)點(diǎn)的處理延時(shí)作了仿真分析，如圖9所示。可以發(fā)現(xiàn)，擁塞態(tài)下網(wǎng)絡(luò)節(jié)點(diǎn)的處理延時(shí)也呈現(xiàn)了1/f噪聲特性。這是因?yàn)榫W(wǎng)絡(luò)在擁塞狀態(tài)下，由于TCP擁塞控制機(jī)制的作用，很多節(jié)點(diǎn)都在排隊(duì)等待確認(rèn)ACK。而目的節(jié)點(diǎn)也要等待自己的數(shù)據(jù)發(fā)出去以后隊(duì)列有空閑時(shí)，才能給源節(jié)點(diǎn)發(fā)出確認(rèn)ACK。因此這導(dǎo)致了擁塞態(tài)下的處理延時(shí)是相互牽制的，呈現(xiàn)出了這種長(zhǎng)相關(guān)特性。

3.3 網(wǎng)絡(luò)局部與整體負(fù)載特性的關(guān)系

網(wǎng)絡(luò)的無(wú)邊界使得研究者不能去模擬整個(gè)網(wǎng)絡(luò)，因此研究網(wǎng)絡(luò)的局部特性與整體特性的關(guān)系就成了研究大規(guī)模網(wǎng)絡(luò)演進(jìn)的一個(gè)有效手段。在擁塞態(tài)下對(duì)網(wǎng)絡(luò)的局部特性與整體特性作了比較，如圖10，從L=32的元胞自動(dòng)機(jī)中抽取一小塊作為研究對(duì)象。仿真結(jié)果如圖11所示:(a)代表L=32的網(wǎng)絡(luò)，(d)代表L=8的獨(dú)立網(wǎng)絡(luò);(b)和(c)分別代表在L=32中截取的(3～10，L=8)的部分小塊網(wǎng)絡(luò)和(15～30，L=16)的部分小塊網(wǎng)絡(luò)。從圖中可以看出，局部的規(guī)模越大，特性越接近整體的網(wǎng)絡(luò)特性。當(dāng)L=16時(shí)，除了幅度的差別外，流量特性的趨勢(shì)已經(jīng)與整體網(wǎng)絡(luò)很接近。因此利用元胞自動(dòng)機(jī)模型，可以通過(guò)局部的平均負(fù)載特性近似觀察整個(gè)網(wǎng)絡(luò)的平均負(fù)載特性。這對(duì)研究大規(guī)模網(wǎng)絡(luò)特性是非常有意義的。

4 結(jié)束語(yǔ)

本文提出了一種基于TCP/IP擁塞控制協(xié)議的二維元胞自動(dòng)機(jī)模型，對(duì)元胞節(jié)點(diǎn)排隊(duì)長(zhǎng)度進(jìn)行限制，并加入瓶頸節(jié)點(diǎn)，使得模型與真實(shí)的網(wǎng)絡(luò)模型更加接近。而且利用此模型對(duì)網(wǎng)絡(luò)在擁塞態(tài)下的平均負(fù)載特性和延時(shí)特性作了分析，克服了現(xiàn)有元胞自動(dòng)機(jī)建模中的轉(zhuǎn)發(fā)過(guò)程隨機(jī)化、缺少擁塞控制機(jī)制、缺少網(wǎng)絡(luò)擁塞態(tài)分析等不足。表1歸納了本文提出的元胞自動(dòng)機(jī)網(wǎng)絡(luò)模型與已有研究的不同和改進(jìn)，并基于此模型的研究得到了如下結(jié)論:a)擁塞態(tài)下，流量功率譜整體呈現(xiàn)1/f噪聲特性，但是與自由流相態(tài)下不同，這種特性會(huì)隨著網(wǎng)絡(luò)擁塞的加重，1/f噪聲特性減弱;b)受TCP擁塞控制機(jī)制的影響，擁塞態(tài)下的節(jié)點(diǎn)處理延時(shí)是相互牽制的;c)利用此模型觀測(cè)到，達(dá)到一定規(guī)模的局部網(wǎng)絡(luò)負(fù)載特性，能夠近似描述整體網(wǎng)絡(luò)的負(fù)載特性。

表1 算法及結(jié)論比較

比較項(xiàng)一維元胞自動(dòng)機(jī)模型現(xiàn)有的二維元胞自動(dòng)機(jī)模型本文模型

自由態(tài)1/f噪聲特性1/f噪聲特性1/f噪聲特性

擁塞態(tài)白噪聲特性無(wú)負(fù)載、延時(shí)特性分析;局部整體分析;網(wǎng)絡(luò)擁塞觀測(cè);

結(jié)構(gòu)引入隨機(jī)化過(guò)程同構(gòu)型:節(jié)點(diǎn)緩存無(wú)限;TCP/IP未起到擁塞控制作用異構(gòu)型:設(shè)置緩沖有限的元胞，引入瓶頸元胞

參考文獻(xiàn):

[1]MOUSTAFA H， LABIOD H， GODLEWSKI P. A reactive random graph (RRG) model for multicast routing in MANETs[C]//Proc of the 48th GLOBECOM.2005:2720-2724.

[2] MANFREDI S， DI BERNARDO M， GAROFALO F. Small world effects in networks: an engineering interpretation[C]//Proc of the 2004 International Symposium on Circuits and Systems. Piscataway， NJ: IEEE，2004:820-823.

[3]TORSTEN H， ROBERT B， WOLFGANG K， et al. A microscopic model for packet transport in the Internet[J]. Physica A， 2001， 294(1): 249-256.

[4]劉鋒， 任勇， 山秀明. 互聯(lián)網(wǎng)絡(luò)數(shù)據(jù)包傳輸?shù)囊环N簡(jiǎn)單元胞自動(dòng)機(jī)模型[J]. 物理學(xué)報(bào)， 2002， 51(6):1175-1180.

[5]袁堅(jiān)， 任勇， 山秀明. 一種計(jì)算機(jī)網(wǎng)絡(luò)的元胞自動(dòng)機(jī)模型及分析[J]. 物理學(xué)報(bào)， 2000， 49(3):398-402.

[6]JIAN Y， KEVIN M. Exploring collective dynamics in communication networks[J]. Journal of Research of the National Institute of Standards and Technology，2002，107(2): 179-191.

[7]金琴芳. 一種基于元胞自動(dòng)機(jī)的自調(diào)節(jié)的網(wǎng)絡(luò)模型[D].南京:南京理工大學(xué)，2005.

[8]ZHILIANG R， ZHIDONG D， DIANXUN S， et al. Analysis of power spectrum and 1/f type power law in a complex computer network model[J]. Computer Physics Communications，2001，136(3): 225-235.