董广智，由 佳，王 战

(海军大连舰艇学院，辽宁 大连 116001)

1 引言

作为近几年的热点研究课题，自适应网络[1]已经逐渐演变成一种重要的网络模式，凭借灵活性、自适应性、可扩展性等诸多优势，在众多传统网络模式中脱颖而出。由于该网络模式下各节点既是服务器也是客户机，其拓扑结构因自适应调整而始终处于动态变化中，并在各个节点上实现数据、带宽、储存空间等资源的共享。自适应网络的独特属性令处理能力较差的节点在高负载状态下，偶有拥塞现象[2]发生，而强处理能力节点则大部分处于空闲状态，这种情况使网络搜索性能受到严重影响。

基于上述研究背景，提出一种自适应网络断边重连方法，通过充分利用节点的处理能力，断开当前的网络连边，重新与另一个邻域节点相连，来平衡网络负载。为应对自适应网络的灵活性与自适应性，将在网络各主机间迁移不受限的移动agent作为断边重连的技术支撑，构建适用于自适应网络的移动agent基本框架，用其动态变化的物理位置抑制网络的自适应属性；利用移动agent的移动性与自主性，赋予节点在主机环境中不断移动的能力与自身状态保持的能力，为节点提供断边重连的决策依据，令网络分流更高效；引用极小连通支配集，有助于降低冗余转发节点数量，提高方法的执行速率。

2 适用于自适应网络的移动agent基本框架构建

利用移动agent及服务器构建出移动agent的基本框架，如图1所示。通过代理传输协议，服务器不仅让agent迁移于各个主机之间，还实现了执行环境与服务接口的供给。在服务器执行agent的过程中，利用代理通信语言对移动agent服务器的服务提出访问申请。

图1 移动agent基本框架

位于移动agent基本框架中最外层的是agent与外界的通信载体，即：安全措施库与代理监听接口。其功能是运行agent的安全举措，屏蔽外界提出的非法访问请求。

中间层的环境交互单元采用代理通信语言，令具有不同语言的代理与服务器保持有效交互与协调，使通信内容语义不受代理通信语言限制。

工作单元含有执行部分及其依据，其中，知识库作为agent的感知部分，具有存储知识与工作结构的能力，该知识与结构由移动阶段生成；agent运行阶段的当前状态即内部状态，对agent的工作执行有一定的影响，反言之，工作执行也对内部状态有一定的约束力；agent建立者设定的站点滞留时间、工作完成度等条件即约束条件，具有确保agent性能得到充分发挥的作用；移动agent路由的决定性因素为路由方案[3]，一般分为静态服务设施列表与规则下动态路由两种，动静态路由方案的选择依据是工作求解阶段的属性。

根据移动agent基本框架设计出以下几种移动agent服务器的基本服务：

1)应用服务：针对比特任务提供一种服务接口；

2)安全服务：形成agent安全运行环境；

3)事件服务：利用代理传输与通信协议，在各个agent之间相互发送事件；

4)目录服务：提供agent位置坐标，得到路由方案；

5)周期服务：建立agent、移动agent、序列化存储agent、分配agent运行环境。

3 自适应网络框架及矢量化处理策略

以独立集的最小连通支配集[4]为基础，架构自适应网络结构，如图2所示，各节点根据最大独立集下最小连通支配集算法[5]，创建对应邻域节点的信息列表。

图2 自适应网络结构示意图

为降低网络复杂度，将节点的局部邻域信息缩小于两跳的界限中。此前需先利用极大独立集的最小连通支配集算法，组建节点集。具体过程为：

首先，根据邻域节点信息选取极小元，采用所选的独立点架构最大独立集；

其次，根据所选支配点，得到极小连通支配集。

该网络全部节点集V的组成部分是极小连通支配集Vp与非支配集Vc，其中，支配节点Vp帮助传输消息。

为保证自适应网络结构能够通过sink节点实现广播功能，设计一种令各支配点与sink节点的间距得以存储的广播算法。该算法的设计理论依据为：对于极大独立集的极小连通支配集，利用sink节点实施广播操作，矢量化处理该自适应网络结构。

假定sink节点的向量值是0，即id(sink).Dsink=0，某节点vi的向量值是Dvi=1，2，…，N，其原始向量值为id(vi).Dvi=∞，则满足如下两个条件：

1)节点vj发送信息massage(id(vj).Dvj，type)给节点vi，当节点vi的向量值Dvi不小于节点vj的向量值Dvj时，Dvi=Dvj+1成立；反之，则告知邻域节点vs；

2)当节点vi属于支配集Vp时，需节点vi把广播转发出去；反之，当其属于非支配集Vc时，只有发现信息中的向量值存在变化，方可告知邻域节点。

4 移动agent下自适应网络断边重连

4.1 断边重连实现步骤

利用构建的移动agent基本框架结构，按照如下流程完成自适应网络的断边重连：

(1)

(2)

其中，网络平均度值可近似为p*N。

2)自适应网络连边。断边重连方法的实现步骤如下所述：

1)以网络内任意一条连边(v1，v2)为目标对象；

2)随机设定节点v1、v2为定点与动点，若定点是节点v1，则动点v2的度值需满足不小于2的条件；

3)针对节点v3任意选择其邻域的一个节点v4。其中，节点v3需有别于节点v1、v2，且邻域节点数量不少于一个；节点v4需有别于节点v1或者v2；

4)将初选连边(v1，v2)断开后，在连边节点v1、v4间添一条连边，实现自适应网络的断边重连。

4.2 网络节点度值分析

由于断边重连的有效实现依据为节点度[6]，因此，需深入分析自适应网络的节点度情况。

假设网络演化时间尺度[7]是t，演化完成后，k度值的节点抽选概率是p(k，t)，则时间尺度从t-1至t的断边重连阶段里，断开连边(v1，v2)、连接连边(v1，v4)的断边重连操作会导致度值k发生变化，使抽选概率转变为p(x，t)，变化的度值就是节点v2的降幅与节点v4的增幅，详细情况如下所述：

1)节点v2度值降幅：该变化幅度包含k+1降至k与k降至k-1两部分。假设节点v2的度值是k，自适应网络的连边个数是M，则该节点的随机选取概率是q1(k)，计算公式如下所示

(3)

2)节点v4度值增幅：该变化幅度包含k-1增至k与k增至k+1两部分。同理得出下列节点v4的随机邻域节点度分布函数表达式

(4)

其中，自适应网络的度分布函数[8]为p(k)。

由此推导出时间尺度t演化终止后的网络主方程式，如下所示

p(k，t+1)-p(k，t)=Wv2+Wv4

(5)

其中，节点v2的降幅是Wv2，节点v4的增幅是Wv4。

若时间尺度趋近于∞，经不断重复后，网络与邻域节点的度分布函数p(k)逐渐平稳，此时有p(k，t+1)-p(k，t)=0，演算出主方程式的最终表达式，如下所示

(k+1)p(k+1)-kp(k)

-kNp2(k)+(k-1)Np2(k-1)=0

(6)

根据该式可以看出，0度值的度分布函数结果也是0，即

p(0)=0

(7)

当度值k取值为1时，有下列表达式

(8)

当度值k大于1时，有下列迭代方程组

(9)

对上列方程组求和，推导出下列表达式

(k+1)p(k+1)-kNp2(k)-2p(2)+Np2(1)=0

(10)

将0度值的度分布函数结果代入上式，得出如下公式

(11)

5 自适应网络断边重连实验分析

在构建的自适应网络框架中添加13000个节点，各节点均存在5个原始邻域节点(即每个节点每次重连时的最多节点数量为5)，其能力分布情况由每个节点上的Gnutella客户端软件获得，如表1所示。

表1 五个原始邻域节点能力分布

5.1 基于集聚系数的自适应网络结构集中程度分析

采用集聚系数反映所建网络结构的集中度，探讨该网络是否具备参与断边重连实验的可行性。整个网络的集聚系数均值计算公式如下所示，网络集中程度随着系数值的增加而提升

(12)

其中，cvi表示节点vi的集聚系数(i=1，2，…，N)，由下式解得

(13)

其中，连接该节点的闭合三角形有svi个，其度值是kvi。

图3为自适应网络集聚系数示意图。

图3 自适应网络集聚系数示意图

根据图3所示的网络集聚系数变化形式可以看出：断边重连概率越大，该移动agent自适应网络的集中性越强，且始终未出现较大波动；但当断边重连概率较小时，网络集中度也呈现出较高水平。这说明构建的自适应网络基于独立集的最小连通支配集，大幅降低了网络复杂度，因为利用sink节点实施广播操作，矢量化处理了自适应网络的结构，所以即便是在小概率断边重连的情况下，依然具有较好的网络集中度，有效地抑制了网络随机性，能够相对可靠地对其断边重连的效果作出检验。

5.2 基于网络负载与度关联的网络断边重连效果分析

该实验环节采用网络负载与度关联两种指标[9]，描述不同断边概率下本文方法断边重连的有效性与准确性。网络负载与度关联指标的计算公式分别如下所示，其中，网络饱和度随着负载数值的减小而下降，有效性越好；度关联指标数值越大，关联度越高，准确度越理想

(14)

(15)

式中，G表示网络吞吐值，d表示网络带宽；连边vi的两个节点度值分别是kvi、kvi+1。

图4为网络负载均衡效果示意图。

图4 网络负载均衡效果示意图

根据图4所示的网络负载变化情况可以看出：随着网络节点数量的持续增加，网络负载指标值大幅下降，证明该方法基于构建的移动agent基本结构，利用最大独立集下最小连通支配集算法，将节点的局部邻域信息成功缩小于两跳的界限中，故具有一定的有效性；当节点数量降至一定程度时，网络负载指标值逐渐趋于平缓且略有上升趋势，说明过多的节点个数会对agent移动路由的动静态方案选取产生较大负担，导致负载均衡操作失效，这点将在今后工作中继续深入探究。

图5为度关联示意图。

图5 度关联示意图

由图5所示的度关联变化形式可以看出，在网络连边数量不断提高的同时，度关联指标值呈线性上扬趋势。这是因为本文方法根据度分布函数与随机邻域节点的度分布函数，深入分析了自适应网络的节点度值，所以才能够在两个具有高关联度的节点间实现重连。

6 结论

复杂网络理论迅猛进步，横跨学科的网络研究范围日益拓宽，这对复杂网络的探索难度提出了前所未有的挑战。随着计算机技术的飞跃式发展，复杂性科学日渐兴起，网络分析的探究方向更是逐渐演变成应用领域中新的里程碑。移动agent模型凭借其自身优势，能够较好地描述个体之间、网络之间的互动关系，故基于此，提出一种自适应网络的断边重连方法。虽然该方法已经初见研究雏形，但仍需从以下几个方面做进一步优化：为满足当前即时性需求，需尝试采用一些主流的智能算法，并将改进计算量(即自适应网络的快速运行)作为下一个讨论课题，加快断边重连的执行速度；应利用社团结构划分算法来改善自适应网络结构，为断边重连的理想实现奠定基础。在今天的技术发展环境下，本文方法经过不断改进与创新，有望成为计算机领域中均衡网络负载的一种有效手段，打破负载给自适应网络带来的局限性。