Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

Compact Routing Schemes for Dynamic Ring Networks

We consider the problem of routing in an asynchronous dynamically changing ring of processors using schemes that minimize the storage space for the routing information. In general, applying static techniques to a dynamic network would require significant re-computation. Moreover, the known dynamic techniques applied to the ring lead to inefficient schemes. In this paper we introduce a new technique, Dynamic Interval Routing, and we show tradeoffs between the stretch factor, the adaptation cost, and the size of the update messages used by routing schemes based upon it. We give three algorithms for rings of maximum size N: the first two are deterministic, one with adaptation cost zero but worst case stretch factor \lfloor N/2 \rfloor, the other with worst case adaptation cost O(N) update messages of O(log N) bits and stretch factor 1. The third algorithm is randomized, uses update messages of size O(k log N), has adaptation cost O(k), and expected stretch factor 1+1/k, for any integer k 3. All schemes require O(log N) bits per node for the routing information and all messages headers are of O(log N) bits.     

Lower Bounds for Dynamic Tree Embedding in Bipartite Networks

There are many parallel computations that are tree structured. The structure of a tree is usually unpredictable at compiler-time; the tree grows gradually during the course of a computation. The dynamic tree embedding problem is to distribute the processes of a parallel computation over processors in a parallel computer such that processors perform roughly the same amount of computation, and that communicating processes are assigned to processors that are close to each other. In this paper, we establish lower bounds for the performance ratio of dynamic tree embedding in bipartite static networks, including numerous important networks such asn-dimensional meshes,n-dimensional tori,k-aryn-cubes, cube-connected cycles, and butterflies. Our lower bounds are obtained from both tree and network properties and are applicable to a general class of dynamic tree embedding algorithms.     

无线传感器网络动态负载均衡树路由算法

多源单汇路由是无线传感器网络的关键问题之一,当所有节点都执行感知任务时,网络流量具有漏斗效应。距离Sink远的节点流量小,距离Sink近的节点由于需要转发大量数据,流量较大,容易产生拥塞。从最小生成树与宽度优先搜索树的特点出发,提出基于动态负载均衡树的路由算法。该算法在初始宽度优先搜索树的基础上,通过嫁接与局部调整树结构的方式,使流量在子树间动态均衡。对Sink位于不同位置的网络进行仿真,结果表明基于动态负载均衡树的路由算法在负载均衡度及能耗方面均占优。     

Constructing Labeling Schemes through Universal Matrices

Let f be a function on pairs of vertices. An f -labeling scheme for a family of graphs ℱ labels the vertices of all graphs in ℱ such that for every graph G∈ℱ and every two vertices u,v∈G, f(u,v) can be inferred by merely inspecting the labels of u and v. The size of a labeling scheme is the maximum number of bits used in a label of any vertex in any graph in ℱ. This paper illustrates that the notion of universal matrices can be used to efficiently construct f-labeling schemes.     

Modelling a Learning-Based Dynamic Tree Routing Model for Wireless Mesh Access Networks

Link asymmetry in wireless mesh access networks (WMAN) of Mobile ad-hoc Networks (MANETs) is due mesh routers’ transmission range. It is depicted as significant research challenges that pose during the design of network protocol in wireless networks. Based on the extensive review, it is noted that the substantial link percentage is symmetric, i.e., many links are unidirectional. It is identified that the synchronous acknowledgement reliability is higher than the asynchronous message. Therefore, the process of establishing bidirectional link quality through asynchronous beacons underrates the link reliability of asymmetric links. It paves the way to exploit an investigation on asymmetric links to enhance network functions through link estimation. Here, a novel Learning-based Dynamic Tree routing (LDTR) model is proposed to improve network performance and delay. For the evaluation of delay measures, asymmetric link, interference, probability of transmission failure is evaluated. The proportion of energy consumed is used for monitoring energy conditions based on the total energy capacity. This learning model is a productive way for resolving the routing issues over the network model during uncertainty. The asymmetric path is chosen to achieve exploitation and exploration iteratively. The learning-based Dynamic Tree routing model is utilized to resolve the multi-objective routing problem. Here, the simulation is done with MATLAB 2020a simulation environment and path with energy-efficiency and lesser E2E delay is evaluated and compared with existing approaches like the Dyna-Q-network model (DQN), asymmetric MAC model (AMAC), and cooperative asymmetric MAC model (CAMAC) model. The simulation outcomes demonstrate that the anticipated LDTR model attains superior network performance compared to others. The average energy consumption is 250 J, packet energy consumption is 6.5 J, PRR is 50 bits/sec, 95% PDR, average delay percentage is 20%.     

基于机会网络的最优化动态合作树选择算法

结点的移动性、传递信息的随机性和无链路连接传递是机会网络的一些信息传递的重要特征,而这些特征与人类社会中人类传递信息的过程极为相似。传统的机会网络算法用于社会网络时会因为环境的变化、人类社会特有的关系属性等问题不能获得很好的效果。因此,本文将随机性、移动性、无连接性等特征作为连接机会网络与社会网络的桥梁,设计了一种选择最优化动态合作树的算法。该算法通过建立动态拓扑结构树的方式,并建立可靠性、可用性、衰减因子、权重因子等作为拓扑结构中的权值进行计算,从而得到最优合作对象和最优合作路径。仿真实验表明,与经典的机会网络算法相比,该算法取得了很好的效果。     

XML 动态区间编码方法

提出了适用于XML文档更新环境下的区间编码方法——DCLS(dynamic containment labeling scheme).DCLS将基于整数的编码泛化到基于向量的编码,扩展了传统静态区间编码方法,有效避免了XML文档更新时的重新编码.不论文档更新与否,DCLS都显示了良好的性能:DCLS利用基于整数的静态区间编码方法进行初始编码,在文档不更新的环境下,具有较高的存储效率和查询性能;同时,DCLS将整数视为特殊向量,不仅能够支持文档更新,而且更新效率高;特别是倾斜插入时,DCLS可以避免编码位长的快速增加.实验结果表明,与已有的动态区间编码方法相比,DCLS具有更好的性能.     

Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

In this paper we introduce a new technique for approximation schemes for geometrical optimization problems. As an example problem, we consider the following variant of the geometric Steiner tree problem. Every point u which is not included in the tree costs a penalty of π(u) units. Furthermore, every Steiner point that we use costs c _S units. The goal is to minimize the total length of the tree plus the penalties. Our technique yields a polynomial time approximation scheme for the problem, if the points lie in the plane. A preliminary version of this paper appeared in the Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2005, 221–232.     

基于序列图模型的多标签序列标注

该文针对实际中存在对同一句话标注多种序列标签问题,定义了多标签序列标注任务,并提出了一种新的序列图模型。序列图模型主要为了建模两种依赖关系:不同单词在时序维度上面的关系和同一单词在不同任务之间的依赖关系。该文采用LSTM或根据Transformer修改设计的模型处理时序维度上的信息传递。同一单词在不同任务之间使用注意力机制处理不同任务之间的依赖关系,以获得每个单词更好的隐状态表示,并作为下次递归处理的输入。实验表明,该模型不仅能够在Ontonotes 5.0数据集上取得更好的结果,而且可以获取不同任务标签之间可解释的依赖关系。     

Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs

δ-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points u,v,w,x, the two larger of the distance sums d(u,v)+d(w,x),d(u,w)+d(v,x),d(u,x)+d(v,w) differ by at most?2δ. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted δ-hyperbolic graphs. Using the Layering Partition technique, we show that every n-vertex δ-hyperbolic graph with δ≥1/2 has an additive O(δlog?n)-spanner with at most O(δn) edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of δ-hyperbolic graphs with an additive error O(δlog?n). The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of n-vertex δ-hyperbolic graphs with δ≥1/2 admits a routing labeling scheme with O(δlog?² n) bit labels, O(δlog?n) additive stretch and O(log?₂(4δ)) time routing protocol, and a distance labeling scheme with O(log?² n) bit labels, O(δlog?n) additive error and constant time distance decoder.     

Performance Analysis for Dynamic Tree Embedding ink-Partite Networks by a Random Walk

We study the problem of dynamic tree embedding ink-partite networksG^kand analyze the performance on interpartition load distribution of the embedding. We show that, for ring-connectedG^k, if the embedding proceeds by taking a unidirectional random walk at a length randomly chosen from [0, Δ − 1], where Δ is a multiple ofk, the best-case performance is achievable at probability e^−k, which is much higher than the asymptotically zero probability at which the worst-case performance may appear. We also show that the same probabilities hold for fully connectedG^kif the embedding proceeds by taking a random walk at a length randomly chosen from [2, ∞). Whenk= 2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have a 50% chance to achieve the best-case performance. We also analyze the performances for embedding in these networks in the expected case and observe the interesting fact that they match the performances in the best case when the network isk-partitionable into partitions of equal size.     

A Dynamic Labeling Scheme for XML Document

Efficient evaluation of XML queries requires the determination of whether a relationship exists between two dements, A number of labeling schemes have been designed to meet the need. However, most of them have poor updating performance. In this paper, a new dynamic region-based labeling scheme is proposed which uses real numbers instead of integers to represent the region. Moreover, the scheme can adjust the codes of some nodes in some parts of the document tree according to the condition of updates. Our analysis shows this new labeling scheme provides efficient support for updates.     

Diffusion Schemes for Load Balancing on Heterogeneous Networks

Several different diffusion schemes have previously been developed for load balancing on homogeneous processor networks. We generalize existing schemes, in order to deal with heterogeneous networks. Generalized schemes may operate efficiently on networks where each processor can have arbitrary computing power, i.e., the load will be balanced proportionally to these powers. The balancing flow that is calculated by schemes for homogeneous networks is minimal with regard to the l ₂ -norm and we prove this to hold true for generalized schemes, too. We demonstrate the usability of generalized schemes by a number of experiments on several heterogeneous networks.     

无线传感器网络节点定位机制的研究

无线传感器网络的许多应用都是基于节点的位置信息。传感器网络由于节点数量巨大,而且资源十分有限,全部节点都采用类似GPS的定位设备是不适宜的。文章介绍了无线传感器网络基于节点之间的连通性来估计节点的位置的定位算法,方法是在传感器网络中预先部署十分少量已知位置信息的信标节点,然后通过节点之间的跳数信息,实现对节点位置的估计。仿真显示该算法具有较好的实用性。     

Simple, Efficient Routing Schemes for All-Optical Networks

All-optical networks promise data transmission rates several orders of magnitude higher than current networks. The key to high transmission rates in these networks is to maintain the signal in optical form, thereby avoiding the prohibitive overhead of conversion to and from the electrical form, and to exploit the large bandwidth of optical fibers by sending many signals at different frequencies along the same optical link. Optical technology, however, is not as mature as electronic technology. Hence it is important to understand how efficiently simple routing elements can be used for all-optical communication. In this paper we consider two types of routing elements. Both types can move messages at different wavelengths to different directions. If in the first type a message wants to use an outgoing link that is already occupied by another message using the same wavelength, the arriving message is eliminated (and therefore has to be rerouted). The second type can evaluate priorities of messages. If more than one message wants to use the same wavelength at the same time, then the message with the highest priority wins. We prove nearly matching upper and lower bounds for the runtime of a simple and efficient protocol for both types of routing elements, and apply our results to meshes, butterflies, and node-symmetric networks. Received January 6, 1998, and in final form July 17, 1998.     

一种高效的动态XML文档树编码机制

针对现有XML编码机制时空效率不高、对XML文档动态更新支持不够等问题,结合素数和IBSL 2种编码机制,提出一种新的XML文档树编码机制——基于素数的二进制字符串编码机制。理论分析和实验均证明该编码机制具有较好的查询效率,能够高效地支持XML文档更新操作,大幅降低空间成本。     

神经网络控制结构及所用神经网络

本文阐述了神经网络控制所能解决的控制难题,若干种控制结构及常用的动态神经网络。讨论了神经网络控制研究的重点,在实时控制中的物理可实现性及其发展等问题。     

传感网节点调度方法综述

节能是传感网的关键问题,而节点调度是延长传感网工作寿命的有效方法。本文建立了节点调度的抽象模型,分析了节点调度方法的设计空间和设计目标,给出了分类方法,并从这两个方面描述了当前典型的节点调度方法,比较了这些方法的特点,最后给出了节点调度方法未来的研究方向。     

A Review of Classification Schemes for Computer Communication Networks

Classification of computer communication networks often depends upon the point of view and background of the person doing the classifying. Network designers, for example, tend to categorize the network according to its switching functioc–rcuit switching, message switch-or packet switching. Managers, who are occupied with economic considerations, look at the topological aspects of a network as centralized, decentralized, or distributed. Finally, network operators are interested in the use of deterministic, stochastic, or flow control routing algorithms, which are methods of routing the message or other communication entity across the network.