The m-pancycle-connectivity of a WK-Recursive network

In this paper, we study the m-pancycle-connectivity of a WK-Recursive network. We show that a WK-Recursive network with amplitude W and level L is strictly (5 × 2^L−1 − 2)-pancycle-connected for W ? 3. That is, each pair of vertices in a WK-recursive network with amplitude greater than or equal to 3 resides in a common cycle of every length ranging from 5 × 2^L−1 − 2 to N, where N is the size of the interconnection network; and the value 5 × 2^L−1 − 2 reaches the lower bound of the problem.     

基于传输范围覆盖的无线传感器网络广播算法

广播在无线传感器网络中具有广泛的应用.泛洪广播虽然简单,但极为耗能.基于概率、基于计数以及基于位置等广播算法不使用任何邻节点信息,简单但性能改善有限.MPR以及多数基于连通支配集的广播算法利用2-hop邻节点信息计算转发节点集,虽然获得了较好的性能,但需更多的通信开销以获取和维护2-hop邻节点信息.为减少转发节点并节约通信开销,较好的实现无线传感器网络广播,本文利用1-hop邻节点信息提出了一种基于传输范围覆盖的广播算法TRCB.算法的主要思想是如果发送节点U的1-hop邻节点V被U和不包括节点V的其余1-hop邻节点集S覆盖,则节点V将不参与转发.分析与仿真表明,TRCB有效减少了冗余转发节点,从而节约了无线传感器网络能耗;并且利用1-hop邻节点信息,具有通信开销小、适应网络拓扑变化的特点;且其性能优于同样利用1-hop邻节点信息的边缘转发算法EFB.     

移动自组网中非完全信息节点风险评估

移动自组网是一种无中心、自组织以及多跳的无线网络,能否有效可靠地对通信节点进行风险评估是保障节点高质量通信的重要因素.当前基于可信度或是信誉的评估方法对评估样本都有特殊的要求,对评估对象提出种种假设,无法辨别间接样本的恶意推荐问题,在实际移动自组网中各个节点尤其是恶意节点对外暴漏的信息往往偏少,样本数量有限,无法明确判断其状态,大部分是非完全信息,从而导致评估结果缺乏客观性与可靠性.文中提出采用灰色系统理论描述通信节点非完全信息状态,根据灰类白化以及灰色聚类思想进行节点风险评估.方案针对自组网络通信需求对节点行为进行多关键属性划分,采用味集群方法收集原始样本,避免恶意推荐;将难以用数值精确刻画的关键属性以白化权函数量化,引入灰聚类的概念和计算方法,将实体的通信风险水平定义为实体关键属性值序列针对各评估灰类的聚类评估值,从而得到该实体通信风险水平的相对参考值.分析与实际计算表明该方法是一种适合移动自组网中非完全信息节点风险评估的有效方法.     

Incomplete hypercubes: Algorithms and embeddings

The hypercube, though a popular and versatile architecture, has a major drawback in that its size must be a power of two. In order to alleviate this drawback, Katseff [1988] defined theincomplete hypercube, which allows a hypercube-like architecture to be defined for any number of nodes. In this paper we generalize this definition and introduce the namecomposite hypercube. The main result of our work shows that these incomplete architectures can be used effectively and without the size penalty. In particular, we show how to efficiently implement Fully Normal Algorithms on composite hypercubes. Development of these types of algorithms on composite hypercubes allows us to efficiently execute several algorithms concurrently on a complete hypercube. We also show that many host architectures, such as binary trees, arrays and butterflies, can be optimally embedded into composite hypercubes. These results imply that algorithms originally designed for any such host can be optimally mapped to composite hypercubes. Finally, we show that composite hypercubes exhibit many graph theoretic properties that are common with complete hypercubes. We also present results on efficient representations of composite hypercubes within a complete hypercube. These results are crucial in task allocation and job scheduling problems.This research was supported in part by the National Science Foundation under grant USE-90-52346. A preliminary version of this work appeared in the5th International Parallel Processing Symnposium, May 1991.     

Node-disjoint paths in incomplete WK-recursive networks

The incomplete WK-recursive networks have been recently proposed to relieve the restriction on the sizes of the WK-recursive networks. In this paper, a maximal set of node-disjoint paths is constructed between arbitrary two nodes of an incomplete WK-recursive network. The effectiveness of the constructed paths is verified by both theoretic analysis and extensive experiments. A tight upper bound on the maximal length is suggested. On the other hand, experimental results show that for arbitrary two nodes, the expected maximal length is not greater than twice their distance and about equal to the diameter. When the two nodes are the farthest pair, the maximal length is not greater than twice the diameter and the expected maximal length is not greater than 1.5 times the diameter.     

Circuit-Switched Broadcasting in Multi-Port Multi-Dimensional Torus Networks

The one-to-all broadcast is the most primary collective communication pattern in a multicomputer network. This paper studies this problem in a circuit-switched torus with -port capability, where a node can simultaneously send and receive messages at one time. This is a generalization of the one-port and all-port models. We show how to efficiently perform broadcast in tori of any dimension, any size, square or nonsquare, using near optimal numbers of steps. The main techniques used are: (i) a span-by-dimension approach, which makes our solution scalable to torus dimensions, and (ii) a squeeze-then-expand approach, which makes possible solving the difficult cases where tori are non-square. Existing results, as compared to ours, can only solve very restricted sizes or dimensions of tori, or use more numbers of steps.     

墙式网孔

提出了一种新的网孔－墙式网孔．墙式网孔是一种三度网孔,它通过从普通四度网孔的每个节点删去一度而获得,其节点度节省了２５％,但其直径同普通四度网孔几乎一样．它在计算能力上同普通四度网孔是等价的,因为四度网孔可以有效地嵌入到墙式网孔中,其伸张度为３,拥塞度为４．于是所有现存的基于四度网孔的并行算法都可以毫不费力地移植到三度网孔中且只有常数的减速比．墙式网孔可以通过边界节点回卷相连而产生墙式环托,它是点     

Localized Techniques for Broadcasting in Wireless Sensor Networks

In this paper we tackle the problem of designing simple, localized, low energy consuming, reliable protocols for one-to-all communication in large scale wireless sensor networks. Our first proposed technique, called the Irrigator protocol, relies on the idea to first build a sparse overlay network, and then flood over it. The overlay network is set up by means of a simple, distributed, localized probabilistic protocol and spans all the sensor nodes with high probability. Based on the algorithmic ideas of the Irrigator protocol we then develop a second protocol, dubbed Fireworks, with similar performance that does not require any overlay network to be set up in advance. Asymptotic analytical results are provided which assess the reliability of the Irrigator and Fireworks techniques. The theoretical analysis of the proposed protocols is complemented and validated by a (simulation based) comparative performance evaluation that assesses several advantages of our new protocols with respect to gossiping and simple flooding. Differently from previous studies, we analyze and demonstrate the performance of our protocols for two different node distributions: The typical uniform distribution and a newly defined “hill” distribution, here introduced to capture some of the important and more realistic aspects of node deployment in heterogeneous terrain. Simulation results show that the proposed schemes achieve very good trade-offs between low overhead, low energy consumption and high reliability. In particular, the Irrigator and Fireworks protocols are more reliable than gossiping, and significantly reduce the number of links along which a message is sent over both flooding and gossiping.     

Training Algorithm with Incomplete Data for Feed-Forward Neural Networks

A new algorithm is developed to train feed-forward neural networks for non-linear input-to-output mappings with small incomplete data in arbitrary distributions. The developed Training-EStimation-Training (TEST) algorithm consists of 3 steps, i.e., (1) training with the complete portion of the training data set, (2) estimation of the missing attributes with the trained neural networks, and (3) re-training the neural networks with the whole data set. Error back propagation is still applicable to estimate the missing attributes. Unlike other training methods with missing data, it does not assume data distribution models which may not be appropriate for small training data. The developed TEST algorithm is first tested for the Iris benchmark data. By randomly removing some attributes from the complete data set and estimating the values latter, accuracy of the TEST algorithm is demonstrated. Then it is applied to the Diabetes benchmark data, of which about 50% contains missing attributes. Compared with other existing algorithms, the proposed TEST algorithm results in much better recognition accuracy for test data.     

Study of General Icomplete Star Interconnection Networks

The star networks,which were originally proposed by Akers and Harel,have suffered from a rigorous restriction on the number of nodes.The general incomplete star networks(GISN) are proposed in this paper to relieve this restriction.An efficient labeling scheme for GISN is given,and routing and broadcasting algorithms are also presented for GIS.The communication diameter of GISN is shown to be bounded by 4n-7.The proposed single node broadcasting algorithm is optimal with respect to time complexity O(nlog2n).     

互连网络局部迭代负载平衡技术

新的基于网络的计算模式（如网格计算,云计算,P2P计算）的共同特点是计算节点之间都是通过互连网络进行通信。对互连网络各个计算节点产生的工作负载进行平衡是提高计算系统性能的关键。文章介绍了近年来在互连网络上使用局部迭代方式求解负载平衡问题在算法设计及其性能分析反面的若干基本研究成果。     

二进制立方形递归网络的拓扑结构

二进制递归网络是一类具有良好拓扑性质和网络参数的互连网络模型.定义了一类特殊的二进制递归网络模型,即二进制立方形递归网络; 引入子网和超网的概念对其拓扑结构进行了分析研究; 证明了超立方体、扭n-立方体、广义扭立方体、交叉立方体、Mbius立方体和扭立方体连接网络都是这类特殊的二进制递归网络的具体实例.     

基于Hopfield神经网络的WSN分布式拓扑

提出一种基于Hopfield神经网络模型的传感器网络的分布式广播算法。在已有网络拓扑的基础上对其数据获取方式进行改进。用优化的Hopfield神经网络模型在各簇中分别从广播源点开始遍历所有传感节点,并返回广播源点的最优链路。利用Hopfield神经网络收敛速率快、通信路径最优,且易于硬件电路实现的特点,形成了能量消耗较少、延时较小的WSN网络,它是一种能量高效的网络。     

Hamiltonian connectivity of the WK-recursive network with faulty nodes

A graph G is said to be Hamiltonian-connected if there is a Hamiltonian path between every two distinct nodes of G. Let F denote the set of faulty nodes of G. Then, G is |F|-node Hamiltonian-connected if G-F is Hamiltonian-connected. We use K(d,t) to denote a WK-recursive network of level t, each of whose basic modules is a d-node complete graph. Compared with other networks, it is rather difficult to construct a Hamiltonian path between two arbitrary nodes in a faulty WK-recursive network. In this paper, we show that K(d,t) is (d-4)-node Hamiltonian-connected. Since the connectivity of K(d,t) is d-1, the result is optimal in the worst case.     

Performance Analysis of Banyan-Type Multistage Interconnection Networks Under Nonuniform Traffic Pattern

Multistage Interconnection Networks(MINs) have a number of applications in the areas of computer and communications. The most widely researched structure among MINs is the (1)banyan type network. It has several variations such as buffered banyan, batcher-banyan, tandem banyan, recirculating banyan and banyan with contention resolution phase. Analytical performance evaluation is crucial for justifying the merit of the design in different operational conditions. While several analytical models have been proposed for the performance evaluation of MINs, they are mainly for uniform traffics. Even the models for nonuniform traffics have several shortcomings such as they only consider output buffered structure or do not consider blocking conditions.In this paper, the more accurate models than any other ones so far have been proposed for the performance evaluation of multibuffered banyan-type MINs under nonuniform traffic condition is obtained. The accuracy of proposed models are conformed by comparing with the results from simulation.Firstly, single buffer model is developed. Markov chain is used for the analysis. Multibuffer model is obtained from single buffer model. Simulation is performed using Discrete Evenet Simulaton(DES) method. As a results, proposed model proves to be very accurate.     

蜂窝环上的全广播算法*

主要研究蜂窝环上的全广播路由算法.第一个全广播算法的设计思路是找到一条通过所有节点的路径,关键是确定边界上的一些特殊节点;第二个全广播算法应用了蜂窝环的哈密尔顿性质.假设一个有n个处理机的蜂窝环,前者每个节点有自己专用的路由策略,时间复杂度为3n,因为计算时间往往比数据传送时间低得多,所以总的通信时间可以降低到n;后者...     

CRN中基于单位圆盘图模型的广播调度算法

广播调度是目前认知无线电网络中的研究热点之一,现有广播调度算法主要为近似算法,存在方案性能与最优解方案差距太大的问题。为此,提出一种基于单位圆盘图模型的广播调度算法BS-UDGM。构建一棵基于连通支配集的广播树,作为调度的基础结构,采用平面细分和着色技术对广播树进行优化,通过混合使用单播和广播通信模式,完成广播任务。仿真实验结果表明,相比其他调度算法,该算法在延时和冗余方面的性能明显提高。     

一类层次双环网络的构造及其路由算法

高效互联网络的拓扑结构一直是人们关注的热点问题。提出了一类层次双环互联网络HDRN（k）,给出了HDRN（k）网络的构造方法,研究了它的性质,并且通过与相关网络的比较,证实了HDRN（k）具有好的连接性、短的直径以及简单的拓扑结构,是一种实用的互联网络。另外,讨论了HDRN（k）网络的路由性质,设计了点点路由和Broadcast路由算法,证明了这两种路由算法的通信效率与层次环网络上对应算法的通信效率相比均有明显的提高。综上所述,HDRN（k）是一种具有良好拓扑性质的新型互联网络。     

Ad hoc网络中的自适应退避算法的研究

本文提出了一种适用于高等级节点的二进制负指数退避算法BNEB,验证了竞争窗口平均值较小的节点信道竞争能力较强的结论,并根据此结论,针对多跳Ad hoc网络中由于MAC层竞争导致的拥塞问题提出了两种具有拥塞控制功能的退避算法RBAB和CABEB,在节点发生拥塞时调整其分组进入速率和转发速率,能够提高网络的端到端吞吐量并有效缓解网络拥塞。     

一种分发车用安全信息的单跳广播协议

单跳广播是分发车用安全信息的基本方法。在车用安全信息广播中,预约信道机制和信道状态指示机制是影响安全信息及时可靠传输的关键问题。本文首先研究了现有的信道预约机制和信道状态指示机制,分析了其对于车用安全信息分发的局限性,提出了一种利用忙音预约一跳信道、指示一跳信道状态的单跳广播协议,并在OPNET网络仿真平台上,进行了仿真实验。实验结果表明,和没有预约信道、以及预约两跳信道的单跳广播协议相比,本文提出的单跳广播协议的性能稳健性较好,更适合于分发车用安全信息。