按信包传递最小普查图研究

普查是信息网络中结点之间的一种常见的也是重要的信息传递方式，在普查过程中，网络所有结点的信息按一定的约束条件传递到终结点。本文定义并讨论了按信包传递最小普查图ｐ－ｍｅｇ，给出了最小普查时间ｔｐ（ｎ）的公式，在讨论了最小普查图与最小广播图的关系之后，指出了识别一个图是否为最小普查图的问题是ＮＰ完全问题，而且对ｐ＝１，２，３完全解决了ｐ－ｍｅｇ的构造问题，对ｐ＝２＾ｋ给出ｎ＝ｍ．２＾ｋ时ｐ－ｍｅｇ的构     

基于扩展安全级的Torus网络容错路由算法研究

在存在故障结点的网络中如何设计最小容错路由是网络容错研究中的一个热点问题。以存在矩形故障块的二维Torus网络为例,将扩展安全级运用到Torus中,对于网络中任意一对结点,给出存在最小路径的充要条件;并且结合扩展安全级的概念,给出建立最小通路区的方法,并用实验验证了方法的可行性。研究为存在故障结点的Torus网络寻找最小容错路径提供了理论依据。     

基于本体概念关联度的信息匹配模型及算法

当今信息查询系统可以借助语义网中的本体在结点之间的信息查询中引入必要的语义,但这种方法在分布式网络中并不完全适用。因此论文主要提出了在分布式网络中借助本体的框架通过使用近义词和概念关联度的概念进行信息查询的新方法,从而在分布式网络中只通过对方和本身结点的有效信息就能进行相对较为有效的信息查询。     

无线传感器网络中基于多向量的拥塞控制

由于无线传感器网络结点分发信息非常方便，因此它在军事和智能居家领域有着广泛的应用前景。如何在这些网络中建立公平、高效、节能的传轮机制将数据汇集到基站是该网络中的一个重要问题。本文提出了一种分布式动态的对不同的路由路径建立多向量信号控制的算法。该算法同时考虑了不同结点的流量，子结点的数目以及子结点的层数等，并将信息快速反馈到检测到的拥塞中，从而迅速缓解拥塞。模拟实验结果和分析表明该机制具有公平性、有效性、稳定性和节能性。     

基于访问控制模块与原始信息注入的图像描述

近年来在图像描述领域对于应用场景图生成描述的研究越来越广泛. 然而, 当前基于场景图的图像描述模型并未考虑到长短期记忆神经网络(LSTM)对于先前输入的细节信息的保留, 这可能会导致细节信息的丢失. 针对这个问题, 本文提出基于原始信息注入的图像描述网络, 该网络对基线模型中语言LSTM的输入变量做了改进, 目的是尽可能多地保留原始输入信息, 减少输入信息在计算过程中的损失. 另外, 本文还认为当前的场景图更新机制中存在结点更新程度过大的问题, 因此本文设计了一个访问控制模块更新已访问过的结点权重, 避免引起结点信息丢失的问题. 同时, 本文设计一个图更新系数(GUF)来指导图更新, 以确定更新程度的大小. 本文在官方数据集MSCOCO上进行了实验, 各种评估机制的实验结果表明, 基于访问控制模块与原始信息注入的图像描述模型与基线模型对比, 取得了更有竞争力的结果, 表现出明显的优越性.     

基于稳定分级结构的移动Ad Hoc网多播路由协议

分级结构适用于大规模移动Ad Hoc网络（MANET），但是分级拓扑结构难以维持，并且MANET的移动性带来了结点通信的稳定性和通信开销问题。该文提出了MHSR协议以形成分级拓扑结构，并引入“逻辑代价”的概念，在此基础上寻找源结点和目的结点问“逻辑代价”总和最小的路径，以达到在网络稳定性得到充分保证的情况下降低通信开销的目的。     

用于通信网阻塞控制的信度网模型

1.引言阻塞是通信网中的一种常见现象。网络由于信息流特性的可变性和网络结点的特性,使得信息在通过结点时产生滞留现象,从而造成信息的时延增大和信息丢失率上升。这种由于网络结点吞吐率下降而引起的信息聚集于一些结点的缓冲区中,网络时延极大增加的现象即为网络的阻塞现象。当网络中一个结点处于阻塞状态,那么与该结     

基于子网的三维Mesh网络容错广播路由算法

在并行计算机系统中,广播通信是极为重要的通信模式之一。该文基于k-Mesh子网(子立方体)连通的概念提出一个基于局部信息和分布式的三维Mesh网络容错广播路由算法。该算法利用邻结点的状态信息,动态地构建以单个k-Mesh子网为结点的广播树,该广播树能容忍相当多的结点出错。模拟结果表明广播路由算法的广播时间步接近最优的。该算法只要求结点知道它的邻结点的状态,而无需知道整个网络状态信息,也就是说,这些算法是基于局部信息的,因而具有很好的实际意义。     

双网络中影响力凝聚子图发现算法

双网络由物理图和概念图构成，其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系；概念图中边表示结点间的相似程度，通常由计算得出.最近，从双网络中发现凝聚子图，即物理图中连通且概念图中稠密的子图受到研究者的广泛关注，在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此：1）提出一种基于最小边权重定义的影响力凝聚子图，即影响力k-连通truss(k-ICT)子图模型.k-ICT子图模型能够有效刻画子图在双网络中的重要性且对低影响力边鲁棒. 2）由证明可知，发现影响力最大的k-ICT子图是NP-难的，因此提出一种基于概念图边等价类划分的CT索引结构.利用索引的概要图，能够根据不同的k值，快速发现包含所有k-ICT子图的候选子图. 3）提出了基于全局枚举删除和局部子图扩展的精确算法Exact-G kICT和Exact-LkICT，用于发现top-r具有最大影响力的k-ICT子图.通过大量在真实数据集上的实验，验证算法的高效性和有效性.     

基于父结点的信息预报马尔可夫模型

节点扰动（churn）是制约P2P系统性能的重要原因,当移动结点（用户）进入P2P网络中（点播或直播）观看节目时,其它节点对其进行数据块传送具有不确定性。本文在以前建立移动结点信息预报的马尔可夫模型基础上,基于父结点建立信息预报马尔可夫模型,从另一个角度对父结点传信息给移动结点的概率进行评估,最后用理论和实验证明了父结点信息传送的概率稳定度。     

Multihop all-to-all broadcast on WDM optical networks

Wavelength-division multiplexing (WDM) optical networks provide huge bandwidth by allowing multiple data streams transmitted simultaneously along the same optical fiber, with each stream assigned a distinct wavelength. A key issue on WDM optical networks is to minimize the number of wavelengths for communications. All-to-all broadcast (gossiping) is a fundamental communication application on computer/communication networks. It is known that the minimum numbers of wavelengths for realizing gossiping in one-hop of optical routing on the ring and the two-dimensional torus of N nodes are cN/sup 2/ and cN/sup 3/2/, c /spl ap/ 1/8, respectively. These numbers can be too large even for moderate values of N. One approach to reduce the number of wavelengths is to realize gossiping in multihops of routing. We give routing algorithms which realize gossiping in k-hops (k /spl ges/ 2) by O(N/sup 1+1/k/) wavelengths on the ring, O(N/sup 1+1/(2k)/) wavelengths on the 2D torus, and O(N/sup 1+1/(3k)/) wavelengths on the 3D torus on a simple multihop routing model. We also discuss the multihop routing for gossiping on a merge model. We give the upper bounds on the numbers of wavelengths for gossiping in two-hops and three-hops for the ring, 2D torus, and 3D torus on the merge model.     

Gossiping protocols for hybrid grid resource scheduling

Grid resource providers can use gossiping to disseminate their available resource state to remote regions of the grid to attract application load. Pairwise gossiping protocols exchange information about limited subsets of other resources between pairs of potentially remote participants. In epidemic gossiping protocols, the provider disseminates information to multiple neighbors, who in turn forward it to their neighbors, and so on. One important metric for these protocols is their coverage, which characterizes how many and which resources receive the information. Coverage characteristics of epidemic protocols are non-uniform, concentrated within the vicinity of a disseminating node; they can exhibit bi-modal behavior where information either reaches distant nodes or dies out quickly. Pairwise gossiping protocols, on the other hand, provide a more uniform coverage, but it can take longer for the dissemination to reach desired uniformity. In this paper, we study performance characteristics of three gossiping protocols: (1) epidemic gossiping, (2) pairwise gossiping, and (3) adaptive information dissemination (which is based on a form of epidemic gossiping). We report experimental results based on our simulation framework that compare the three protocols in terms of packet overhead and query satisfaction rates. We show that pairwise gossiping protocols work best when resource distribution on the grid is uniform, and that they can be configured to perform well in support of grid scheduling. We also verify this behavior under typical node failures of real-world production grids.     

Optimal algorithms for dissemination of information in some interconnection networks

The problems of gossiping and broadcasting in one-way communication mode are considered for some prominent families of graphs. The complexity is measured as the number of communication rounds in the gossip and broadcast algorithms. The main result of the paper is the precise estimation of the gossip-problem complexity in cycles. To obtain this result a new combinatorial analysis of gossiping in cycles is developed. This analysis leads to an optimal lower bound on the number of rounds, and also to the design of an optimal algorithm for gossiping in cycles. The optimal algorithm for gossiping is later used to design new, effective algorithms for gossiping in important families of interconnection networks (cube connected cycles, butterfly networks). Furthermore, a new, effective algorithm for broadcasting in shuffle-exchange networks is developed.On leave from Comenius University, Bratislava, Czechoslovakia.     

Optimal information dissemination in star and pancake networks

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N=n! processors, our algorithms take less than [log N]+1.5n steps     

An O(n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks

We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D , we present an adaptive deterministic gossiping algorithm of time O ($\sqrt{D}$ n+n log 2 n ) or O(n 1.5) . This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor.     

ANALYSIS OF GOSSIPING ALGORITHMS WITH RESTRICTED BUFFERS

In this paper we present a new algorithm for gossiping in distributed-memory parallel architectures whose interconnection network is a two-dimensional torus. The results are presented for odd-sized square torus, but the extensions are discussed at the end of the paper. The gossiping communication routine corresponds to simultaneous broadcasts at each node. In this study we assume a store-and-forward routing mechanism where all processors send a message of same length on each link during the time step. As we briefly discuss at the end, this holds also for circuit-switched routing for large messages.

The main result of this work is to establish a general lower bound for gossiping in a square torus and to analyze the influence of buffering. After a brief discussion of the existing solutions, we present the principle of a new algorithm. Then, we study its complexity with restricted buffers. This new algorithm is compared with the existing gossiping algorithms from its buffering capabilities and is found to be superior.     

Modeling gossip-based content dissemination and search in distributed networking

This paper presents a rigorous analytic study of gossip-based message dissemination schemes that can be employed for content/service dissemination or discovery in unstructured and distributed networks. When using random gossiping, communication with multiple peers in one gossiping round is allowed. The algorithms studied in this paper are considered under different network conditions, depending on the knowledge of the state of the neighboring nodes in the network. Different node behaviors, with respect to their degree of cooperation and compliance with the gossiping process, are also incorporated. From the exact analysis, several important performance metrics and design parameters are analytically determined. Based on the proposed metrics and parameters, the performance of the gossip-based dissemination or search schemes, as well as the impact of the design parameters, are evaluated.     

Improving the gossiping effectiveness with distributed strategic learning (Invited paper)

Gossiping is a widely known and successful approach to reliable communications, tolerating packet losses and link crashes. It has been extensively used in several middleware kinds, such as event notification services and application domains, like infrastructures for air traffic management, power grid control, health information exchange, just to cite some of them. Despite achieving a high loss-tolerance and scalability degrees, gossiping is affected by degraded performances and heavy traffic loads on the network. For this reason, it may be not optimal in applications where reliability must be provided jointly with timeliness and/or in congestion-prone networks. The crucial aspect for improving a gossiping scheme is deciding which nodes should receive a gossiping message, and our driving idea is to adopt a distributed strategic learning logic to determine such nodes in an efficient manner. This is able to resolve gossiping’s weakness points and to achieve better performance and reduced traffic loads.This paper describes how to introduced strategic learning in a gossip scheme so as to determine the best set of nodes that can be used to send gossip messages and to optimize their utility. Such a solution has been experimentally assessed through a set of simulations demonstrating the effectiveness of the proposal.     

Deterministic Communication in Radio Networks with Large Labels

We study deterministic gossiping in ad hoc radio networks with large node labels. The labels (identifiers) of the nodes come from a domain of size N which may be much larger than the size n of the network (the number of nodes). Most of the work on deterministic communication has been done for the model with small labels which assumes N = O(n). A notable exception is Peleg's paper, where the problem of deterministic communication in ad hoc radio networks with large labels is raised and a deterministic broadcasting algorithm is proposed, which runs in O(n²log n) time for N polynomially large in n. The O(nlog²n)-time deterministic broadcasting algorithm for networks with small labels given by Chrobak et al. implies deterministic O(n log N log n)-time broadcasting and O(n²log²N log n)-time gossiping in networks with large labels. We propose two new deterministic gossiping algorithms for ad hoc radio networks with large labels, which are the first such algorithms with subquadratic time for polynomially large N. More specifically, we propose: a deterministic O(n^3/2log²N log n)-time gossiping algorithm for directed networks; and a deterministic O(n log²N log²n)-time gossiping algorithm for undirected networks.     

Robust Reputation in Decentralized Markets

Establishing cooperation and protecting individuals from selfish and malicious behavior are key goals in open multiagent systems. Incomplete information regarding potential interaction partners can undermine typical cooperation mechanisms such as trust and reputation, particularly in lightweight systems designed for individuals with significant resource constraints. In this article, we (i) propose extending a low‐cost reputation mechanism to use gossiping to mitigate against the effect of incomplete information, (ii) define four simple aggregation strategies for incorporating gossiped information, and (iii) evaluate our model on a variety of synthetic and real‐world topologies and under a range of configurations. We show that (i) gossiping can significantly reduce the potentially detrimental influence of incomplete information and the underlying network structure on lightweight reputation mechanisms, (ii) basing decisions on the most recently received gossip results in up to a 25% reduction in selfishness, and (iii) gossiping is particularly effective at aiding agents with little or no interaction history, such as when first entering a system.