软件学报
JOURNAL OF SOFTWARE
1999年 第10卷 第8期 Vol.10 No.8 1999



分布式虚拟环境中基于神经网络的实时预测
寿黎但 史烈 石教英
摘要　在分布式虚拟环境中,性能的瓶颈是为维护主机间实体行为的一致性而进行的通信.该文针对虚拟场景中的难预测对象建立其状态向量的神经网络模型,使用了基于函数型连接的神经网络对其行为进行实时预测.首先介绍了函数型连接的原理和特点;其次,在对传统的DR算法进行描述后提出了基于神经网络预测的自适应DR算法;然后给出了基于该算法的网络软件结构;最后对一个特例进行了实验,实验结果表明该算法可以很好地工作.
关键词　分布式虚拟环境,计算机网络,Dead Reckoning (DR算法),神经网络,函数型连接.
中图法分类号　TP
Real-time Prediction Based on Neural-networks in Distributed Virtual Environment
SHOU Li-dan SHI Lie SHI Jiao-ying
(State Key Laboratory of CAD&CG Zhejiang University Hangzhou 310027)
(Department of Computer Science and Engineering Zhejiang University Hangzhou 310027)
Abstract　 In a distributed virtual environment (DVE), the bottleneck of performance is the communication among hosts which keeps the consistency of virtual entities. The neural-network models of state vectors for unpredictable entities in a virtual scene are build in this paper, and the functional-link net to real-time prediction of their behavior is applied. Firstly, the principles and characters of functional-link net are introduced in this paper; secondly, after description of the traditional dead reckoning (DR) algorithm, an adaptive version of the algorithm based on functional-link net is presented; the network software architecture based on the algorithm is also given; finally, an example of the algorithm is given with experimental data, which shows the good performance of it.
Key words　Distributed virtual environment, computer networks, dead reckoning, neural-network, functional-link net.
　　分布式虚拟环境(distributed virtual environment)是指,在一组以网络互联的计算机上同时运行虚拟环境(VE)系统的技术.它是虚拟环境与网络技术学科交叉的产物,可以使人们自由地在虚拟环境中实现交互而不受其实际地理位置的制约,从而可在许多科研和应用领域中使用,如远程学习、计算机支持下的协同工作(CSCW)、分布式模拟(distributed simulation)等各种应用.分布式虚拟环境的理论和概念还派生出了许多新的领域,如远程机器人(telerobotics)、远程诊治(telemedicine)等.分布式虚拟环境是目前最热门的研究领域之一,在科学研究、模拟训练、战场仿真等许多方面有广阔的应用前景.
　　在分布式虚拟环境中,最根本的要求是每时每刻都要保持分布式系统各主机间场景和场景中各虚拟实体行为的一致性,以维护整个系统的统一.因此这就需要各主机之间实时地交换大量的状态信息,由此而引起的通信量往往占分布式虚拟环境实体间总通信量的大部分.这一类通信我们称为一致性通信.一致性通信数据的发送者称为参考系统（或标准系统）,接收者称为从属系统.在场景复杂度较高（如数万～数十万实体）或系统规模较大（数百～数千台主机）的情况下［1］,一致性通信往往会导致网络环境的拥塞乃至崩溃.因此,降低一致性通信量是分布式虚拟环境中的一个重要研究课题.
　　近年来已有许多研究工作在该方向上展开［2］［3］,其中常用的方法是采用自动控制理论中的DR算法,对虚拟场景中的实体行为进行预测,减少一致性通信的次数,从而达到降低网络带宽的目的.它们的基本思想是在参考系统和从属系统上采用完全一致的预测算法,根据虚拟实体的状态历史,对下一时刻的状态进行预测.如果预测结果与实际状态相差不远,则在参考系统端不发送下一时刻的一致性数据,从属系统中下一时刻的状态就用预测所得结果代替;反之,若与实际相差较远,则发送实际状态的数据,即进行一致性通信.这类预测所工作的对象一般有一个共同的特征,即其状态向量可用一个简单的时间函数表示.但是实际的虚拟场景中往往存在许多实体,其状态向量无法用一个简单的函数来表示.这类对象一般较智能化,直接受到人的控制,因此,随意性很大.对于这类实体,传统的DR算法无能为力,这就需要另辟途径来对其进行研究.在本文中,我们使用基于函数型连接的神经网络来对虚拟实体进行实时的预测,得到了较好的效果,大大降低了一致性通信量（在本文中,为了避免混淆,我们用网络一词表示多台主机之间的计算机网络,而用神经网络一词表示抽象的人工神经网络）.
1 函数型连接简介
　　在函数型连接模型中,一旦一个节点,例如,节点k被激励,就会有许多附加函数功能也被激励,即不仅能得到节点k的输出ok,而且还能得到f0(ok),f1(ok),...,fn(ok)［4］.对函数型连接的不同具体要求会产生不同的效果.在本文中,我们考虑函数展开模型和张量（或称外积）模型.
　　在函数展开模型中,函数型连接单独作用在每个节点上 对于输入模式中的每个节点,它产生相同的附加函数.在这种情况下,输入x可以简单地展开成它的幂函数,或者是展开成n维空间的正交基函数的一个子集,例如:sinπx,cosπx,sin2πx,cos2πx等等.该神经网络的作用是将输入模式映射到一个更大的模式空间.我们将输入分量与其展开的量联系起来,并用它们来表达输入.这样做没有引入本质性的新信息,但模式表达可以得到增强.
　　在张量或外积模型中,输入模式的每个分量都被乘上整个输入模式矢量.在这种情况下,原来由分量集合{xi}所描述的模式变成{xi,xixj}(其中j≥i)或{xi,xixj,xixjxk}(其中j≥i,k≥j≥i)等等.这样做没有引入新的信息,但是它可使神经网络得到联合激励.
　　在这两种模型中使表达增强的运算可以适当地混用.通过函数变换后的神经网络由于其输入得到了增强,仅使用(规则和单层神经网络就可使学习过程迅速收敛［5］.对输入节点个数不超过5,样本个数较少（10个以内）的小规模学习问题,只需不到100次即可使系统误差小于10-6.例如,考虑一个3输入（x1,x2,x3),单输出(y)的学习问题,7组学习样本见表1.
表1 三输入单输出学习样本集

样本序号x1x2x3y
10.2160.10.10.90
20.3470.160.10.85
30.4630.240.10.80
40.4870.320.30.75
50.5130.400.30.7
60.5470.460.60.65
70.7800.90.60.6


　　可以采用混合型函数展开项x1,x2,x3,x1.x2,x1.x3,x2.x3,cos(3π.x2),cos(3π.x3),cos(18π.x3.x2),cos(13π.x1.x3),cos(13π.x1.x2),cos(24π.x1.x3),cos(24π.x2.x3),cos(24π.x1.x3)等14项,采用单层拓扑结构即可使神经网络迅速收敛,如图1所示.

图1　三因素函数型网络的学习速度
　　从图1中可以看出,在多因素情况下采用扩展的输入项,可使得学习的收敛速度大大提高,同时,该神经网络采用了单层的结构,设计简单,编程方便,学习时间极短（在Pentium 200MHz机器上不到1ms）,因此,可以满足实时预测的需求.
2 基于函数型连接的预测算法
　　在分布式虚拟环境中,已经有许多有关虚拟实体状态向量的预测算法的研究.这类算法统称为DR算法.一个典型的DR预测算法是在参考系统和从属系统两端都使用Kalman预测器［6］,根据其运动的状态方程在每一次时钟周期时检查其预测结果与实际状态的误差,如该误差超过一个约定的阈值,则进行一致性通信,否则省去该次时钟周期内的一致性通信.
　　在动态的虚拟场景中,许多运动实体常常遵循一定的规律运动.但是也有一些实体的运动没有明显的规律可循,即无法用状态方程表示其运动.举一些简单的例子,如鼠标的移动、数据手套的动作等.这些对象的运动往往受到智能型用户的直接控制,因而其状态改变的随意性较大.换句话说,这类对象的状态较难预测.如果将这类对象中的某一个看做一个系统,则往往不可能找到一个确定的状态方程来描述它.此时,我们可以求助于神经网络.
　　在第1节中我们已简单地介绍了基于函数型连接的神经网络.这种神经网络的优越性使得它可胜任实时的预测.算法的基本原理是:对于难预测对象而言,在长时间内其运动状态往往显得较混乱而无规律,但是我们有理由认为（算法的实验也确实表明了这一点）在一段短时间内,对象的运动遵循某种难以确定的规律,这种规律是随着时间而改变的,但是状态对于时间的变化总是连续函数,因此,在有限的自变量范围内,根据有限个样本总可以用若干个确定的正交基函数的线性表示来逼近［5］.这也是函数型连接的理论基础.这些正交基函数正是函数型连接中的函数展开项.例如,提供k组样本集合{(Xm,Xm+1,...,Xm+r-1,ym+r),(Xm+1,Xm+2,...,Xm+r,ym+r+1),(Xm+k-1,Xm+k,...,Xm+k+r-2,ym+k+r-1)},其中ym+i恰好就是Xm+i(i=r,...,k+r-1),则可以选取适当的神经网络,经过学习后使得神经网络输出向量y′m+i与样本集合中的ym+i一致.因此可以看出,这里的每组样本实际上是根据前r个状态,预测第r+1个状态.由该组样本训练而成的神经网络可以用来预测ym+k+r的值.
　　由于对象状态不停地改变,这就需要实时地对预测器进行调整,包括修改学习样本集并进行再学习.这样我们可以在传统的DR算法基础上得到另一种算法,这种算法可以称为基于学习的自适应DR算法.由于自适应DR算法能对运动方程不确定的对象进行预测,因此特别适用于难预测对象.
在给出算法描述之前我们先对符号表示作一些约定:我们用k维向量X=(x1,x2,...,xk)T表示被考察对象的状态向量;用Xn表示tn时刻对象的状态向量.第i组学习样本用含有r+1个状态向量的矩阵S(i)=(Xmi,Xmi+1,...,Xmi+r-1,Y(i))表示,其含义是前r个状态向量预测产生函数型连接的输出状态向量y(i).学习样本集η如下:{S(i)|i=1,2,...,N}.
　　整个系统分为参考端（标准端）和从属端.参考端的预测算法如下.
　　算法1. 参考端的预测算法
　　Step1. 用伪随机数构造样本集η={S(i)|i=1,2,...,N}.
　　Step2. 用该组样本集合对神经网络进行训练学习.
Step3. 将过去的r个时间点的状态历史序列Xn-r+1,Xn-r+2,...,Xn作为函数型神经网络的r个输入,计算输出向量(即预测结果）n+1.
　　Step4. 接收到下一个时间同步信号（tn+1时刻）,如果‖Xn+1-n+1‖＞ε,则将新状态向量Xn+1的数据通过计算机网络环境发送到预测端,并将状态Xn+1加入历史序列,同时用新样本
S=(Xn-r+1,Xn-r+2,...,Xn,Xn+1)
代替η中最老的样本;否则,不发送数据,而将预测向量n+1当作tn+1时刻的状态加入状态历史序列,同时用
S=(Xn-r+1,Xn-r+2,...,Xn)
更新样本集η.
　　Step5. 无条件跳转至Step2,依次无限循环执行Step2～4各步操作.
　　由算法的描述可知,每收到一个时钟信号,算法就循环一次.上述算法的Step3中需要忽略最初的r次循环,因为最初r次循环时不存在长度为r的历史序列.另外,每次循环都要改变相应序列的下标.这些说明同样也适用于从属端的算法.从属端的算法可以表示如下.
　　算法2. 从属端的预测算法
　　Step1. 用与算法1相同的伪随机数构造样本集η={S(i)i=1,2,...,N}.
　　Step2. 用该组样本集合对神经网络进行训练学习.
　　Step3. 将过去的r个时间点的状态历史序列Xn-r+1,Xn-r+2,...,Xn作为函数型神经网络的r个输入,计算输出向量(即预测结果）n+1.
　　Step4. 接收到下一个时间同步信号（tn+1时刻）,如果在此之前收到参考端的数据包,则将收到的新状态Xn+1加入历史序列,同时用新样本
S=(Xn-r+1,Xn-r+2,...,Xn,Xn+1)
代替η中最老的样本;否则,即未收到数据包,则将预测向量n+1当做tn+1时刻的状态加入状态历史序列,同时用
S=(Xn-r+1,Xn-r+2,...,Xn)
更新样本集η.
　　Step5. 无条件跳转至Step2,依次无限循环执行Step2～4各步操作.
3 系统的软件结构
　　根据上节中所给出的算法,我们可以设计出相应的网络软件结构.如图2所示.

图2　基于神经网络
　　对应于一个实体i,参考端主机上有一个神经网络预测器,其内部运行算法1;与它相对应从属端主机上必然存在一个相应的从属实体i′和神经网络预测器,该预测器执行算法2(图中F-LNN是基于函数型连接的神经网络的缩写).由于分布式虚拟环境中主要的性能限制来自网络带宽瓶颈,从该软件结构图可以看出,采用神经网络预测器的实质是用消耗计算资源的方法来降低对网络资源的需求.基于函数型连接的神经网络具有极高的收敛速度（多数情况＜1ms）,因此当实体个数较大时,预测过程所消耗的单机计算资源仍然不多.可见,该预测算法提供了良好的可扩展性,对于目前计算机领域内很热门的大规模分布式虚拟环境［3］（Large-Scale Distributed Virtual Environment）具有参考价值.
4 实验结果
　　由于我们所关心的实体行为是“难以预测”的,实体行为的宏观表现较混乱,所以往往不需要保留很长的状态历史序列,一般只需不到10个.另外,我们所考察的虚拟实体在虚拟空间中函数型连接的学习过程非常迅速,在样本个数不超过10个,只需要100～200次循环学习即可使神经网络收敛.当输入的状态向量个数不超过5个时,这样的计算量在目前的高档PC机上只需不到1ms的时间,因此该算法完全可以用于实时的预测.
　　我们对空间自由度为2的鼠标进行了实验,硬件平台是用10Mbps的以太网互连的20台Pentium 200Mhz的PC机,软件平台采用MS Windows95,实验对象是4名熟练用户.另外,我们对同样的数据使用二次多项式插值来预测作为对照.在该实验的神经网络预测算法中,r值取为2,样本集所含的样本个数N为4.因此,我们可以建立含有二个输入向量,一个输出向量的函数型神经网络.设两个输入向量分别为(xn-1,yn-1)和(xn,yn),则对该两个向量作如下19维的混合型函数展开:xn-1,yn-1,xn,yn,xn-1.yn-1,xn-1.xn,yn-1.xn,xn.yn,xn.yn-1,xn-1.yn,xn.yn,cos(3π.xn-1),cos(3π.yn-1),cos(3π.xn),cos(3π.yn),cos(8π.xn-1.yn-1),cos(8π.xn-1.yn),cos(13π.xn.yn),cos(13π.xn.yn-1),并实时预测新的状态向量(xn+1,yn+1),结果如图3所示.

图3　预测算法对4个用户的鼠标使用的结果
　　实验结果表明,该算法对所有用户所操纵的鼠标都能很好地进行预测,而且该算法的预测精度优于多项式插值的预测算法.产生这种结果的原因是由于神经网络预测器能够实时地修改其权值,使之在不同的时刻进行自适应.在模拟实体数目较大的情况下（例如,103个）,算法可以节省50%～70%的一致性通信量,对所有实体进行一次预测消耗CPU时间2.4～3.0s.但是对于大规模系统(实体数＞105),模拟测试表明,消耗在预测算法上的计算量特别巨大,这就需要强大的单机计算能力的支持.另外,对于传统DR算法的预测对象,即状态可表示为显式时间函数的实体,该神经网络算法也可很好地进行预测,本文不再赘述.
5 结 论
　　（1） 函数型连接是一种采用函数并行激励机制的神经网络,这种神经网络的特点是采用单层拓扑结构和δ学习规则,因而收敛速度非常高.本文给出了一个基于函数型连接的神经网络预测算法用于对分布式虚拟环境中的实体状态进行实时的预测,克服了传统的DR算法对难预测对象无法建立其控制论模型的缺点.实验结果表明,对自由度为二的鼠标,该算法可以很好地工作.
　　（2）在分布式虚拟环境中,主要的性能瓶颈是网络带宽.文中所述的基于函数型连接的神经网络预测算法降低了网络带宽的消耗,有助于提高整个系统的性能和可扩展性.
本文通讯联系人:寿黎但,杭州 310027,浙江大学 CAD&CG 国家重点实验室
作者简介：寿黎但,1974年生,硕士生,主要研究领域为CSCW,多媒体,大规模分布式虚拟环境.史烈,1964年生,讲师,主要研究领域为多媒体,虚拟现实.石教英,1937年生,教授,博士生导师,主要研究领域为计算机图形学,计算机体系结构,虚拟现实.
作者单位：寿黎但　浙江大学 CAD&CG 国家重点实验室 杭州 310027
史烈 石教英　浙江大学计算机科学与工程学系 杭州 310027
参考文献
1 Pentland A P. Computational complexity versus simulated environments. Computer Graphics, 1990,24(2):185～192
2 Pratt D R. A software architecture for the construction and management of real time virtual environments ［Ph.D. Thesis］. Monterey, California: Naval Postgraduate School, 1993
3 Macedonia M R. A network software architecture for large scale virtual environments ［Ph.D Thesis］. Monterey, California: Naval Postgraduate School, 1995
4 (美)包约翰.自适应模式识别与神经网络.北京:科学出版社,1992
(Pao Yoh-han. Adaptive Pattern Recognition and Neural-networks. Massachusetts, Menlo Park: Addison-Wesley Publishing Company Inc., 1989. 192～215)
5 Pao Yoh-han, Yoshiyasu Takefuji. Functional-link net computing: theory, system architecture, and functionalities. Computer, 1992,25(5):76～79
6 Baumgartner, Eric T, Skaar, Steven B. An autonomous vision-based mobile robot. IEEE Transactions on Automatic Control, 1994,39(3):493～502
本文1998-06-02收到原稿,1998-09-16收到修改稿
