非平衡拓扑结构的多智能体网络系统一致性协议

针对多智能体网络系统,本文分别研究了非平衡拓扑结构的多智能体连续状态和离散状态下的一致性协议.首先提出了能使用有向图表示的多智能体网络系统的拓扑结构,并根据该拓扑结构建立了网络系统的1阶数学模型和提出了多智能体网络系统一致收敛准则.对于多智能体网络连续系统,该系统的一致平衡点最终收敛于初始状态的凸组合,本文最终确定了非平衡拓扑结构的一致平衡点.如果多智能体网络系统的拓扑结构没有改变,在离散状态下系统的一致平衡点仍收敛于初始状态的凸组合,并且离散状态下系统的一致平衡点与连续状态下系统的一致平衡点相等.最后采用8个智能体组成的网络拓扑进行计算机仿真,验证理论的正确性.     

一种新的传感器网络混合广播调度方法

由于传感器网络所使用无线信道的共享性和相互干扰, 节点间数据广播会产生资源冲突, 广播调度要解决的即是为每个节点分配到一个无冲突传输时隙, 其目标是找到最优时分复用(TDMA: time division multiple access)调度解, 使得帧长度最短而信道利用率最大. 提出基于神经网络的两阶段混合广播调度算法. 在阶段一, 使用改进的顶点着色算法来获得调度所需最短时隙数目; 在阶段二, 使用模糊Hopfield网络将节点模糊聚类为M类, 同类 节点可以在同一时隙被调度, 不同类节点必须在不同时     

Addressing agent loss in vehicle formations and sensor networks

In this paper, we address the problem of agent loss in vehicle formations and sensor networks via two separate approaches: (1) perform a ‘self‐repair’ operation in the event of agent loss to recover desirable information architecture properties or (2) introduce robustness into the information architecture a priori such that agent loss does not destroy desirable properties. We model the information architecture as a graph G(V, E), where V is a set of vertices representing the agents and E is a set of edges representing information flow amongst the agents. We focus on two properties of the graph called rigidity and global rigidity, which are required for formation shape maintenance and sensor network self‐localization, respectively. For the self‐repair approach, we show that while previous results permit local repair involving only neighbours of the lost agent, the repair cannot always be implemented using only local information. We present new results that can be applied to make the local repair using only local information. We describe implementation and illustrate with algorithms and examples. For the robustness approach, we investigate the structure of graphs with the property that rigidity or global rigidity is preserved after removing any single vertex (we call the property as 2‐vertex‐rigidity or 2‐vertex‐global‐rigidity, respectively). Information architectures with such properties would allow formation shape maintenance or self‐localization to be performed even in the event of agent failure. We review a characterization of a class of 2‐vertex‐rigidity and develop a separate class, making significant strides towards a complete characterization. We also present a characterization of a class of 2‐vertex‐global‐rigidity. Copyright © 2008 John Wiley & Sons, Ltd.     

图的正交(g,f)-因子分解

设ｇ和ｆ分别是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数值函数且对每一个ｘ∈Ｖ（Ｇ）有２≤ｇ（ｘ）≤ｆ（ｘ）．证明了若Ｇ是（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）—图,则对Ｇ中任意一个给定的有ｍ条边的子图Ｈ,Ｇ有一个（ｇ,ｆ）—因子分解与Ｈ正交．     

Stability analysis for multi-agent systems using the incidence matrix: Quantized communication and formation control

The spectral properties of the incidence matrix of the communication graph are exploited to provide solutions to two multi-agent control problems. In particular, we consider the problem of state agreement with quantized communication and the problem of distance-based formation control. In both cases, stabilizing control laws are provided when the communication graph is a tree. It is shown how the relation between tree graphs and the null space of the corresponding incidence matrix encode fundamental properties for these two multi-agent control problems.     

Antimagic labeling and canonical decomposition of graphs

An antimagic labeling of a connected graph with m edges is an injective assignment of labels from {1,…,m} to the edges such that the sums of incident labels are distinct at distinct vertices. Hartsfield and Ringel conjectured that every connected graph other than K₂ has an antimagic labeling. We prove this for the classes of split graphs and graphs decomposable under the canonical decomposition introduced by Tyshkevich. As a consequence, we provide a sufficient condition on graph degree sequences to guarantee an antimagic labeling.     

有向无环图最小度生成树问题的一种近似算法

计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.     

面向攻击图构建的网络连通性分析

针对目前网络攻击图构建系统的需求,设计网络连通性分析算法。通过对网络拓扑及防火墙规则进行离线分析,可以判断网络中由若干台过滤设备分隔的任意2台主机间的连通性。引入关键实体集的概念,结合经典的Apriori算法提出一种快速有效的获取关键实体集的方法。分析对比表明,关键实体集可以在连通性分析过程中为网络中各节点的重要性评估提供有力依据。     

基于可疑行为识别的PE病毒检测方法

针对当前PE病毒难以防范及查杀的现象,对PE病毒关键技术进行分析,提取病毒典型特征的可疑行为,在此基础上提出一种Windows平台下的静态检测方法。该方法在对程序反编译处理的基础上,以指令序列与控制流图的分析为行为识别依据,完成基于可疑行为识别的病毒检测方法的设计。实验结果证明,该检测方法能有效检测混淆变换病毒。     

有限长度LDPC码一种速率兼容删余算法

提出一种AWGN信道下有限长度RC-LDPC码的删余算法,该算法对规则及非规则LDPC码均有效。该删余算法基于一系列准则,其中一个重要准则是某个候选删除节点的具有低的近似环外消息度(ACE)的短环的数量。仿真结果表明,ACE对删余码的性能有很大的影响,该算法的性能比已有算法有进一步提高。