MAP estimation via agreement on trees: message-passing and linear programming

We develop and analyze methods for computing provably optimal maximum a posteriori probability (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and b) a tree-reweighted max-product message-passing algorithm that is related to but distinct from the max-product algorithm. In this way, we establish a connection between a certain LP relaxation of the mode-finding problem and a reweighted form of the max-product (min-sum) message-passing algorithm.     

一种改进的分布式最大权独立集算法

能快速准确寻找给定图中的最大权独立集的分布式算法,对于解决无线网络中的资源调配、无线骨干网构建等问题具有非常重要的指导意义。该文以基于最大乘信用传播的分布式算法为框架,假设所有节点了解自己邻居节点之间的局部拓扑信息,启发式地提出一种新的相邻节点间交换消息的计算方法以及相应的分布式最大权独立集算法。仿真结果表明,所提算法摆脱了文献中已有算法对图结构必须是树或者二分图的要求,且权和性能优于已有的分布式算法。     

Efficient erasure correcting codes

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number ϵ a family of linear codes of rate R which can be encoded in time proportional to ln(1/ϵ) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+ϵ)Rn or more. The recovery algorithm also runs in time proportional to n ln(1/ϵ). Our algorithms have been implemented and work well in practice; various implementation issues are discussed     

On the efficiency of multicast

The average number of joint hops in a shortest-path multicast tree from a root to m arbitrary chosen group member nodes is studied. A general theory for all graphs, hence including the graph representation of the Internet, is presented which quantifies the multicast reduction in network links compared to m times unicast. For two special types of graphs, the random graph G_p(N) and the k-ary tree, exact and asymptotic results are derived. Comparing these explicit results with previously published Internet measurements indicates that the number of routers in the Internet that can be reached from a root grows exponentially in the number of hops with an effective degree of approximately 3.2     

κ‐channel connectivity in cognitive radio networks for bounded tree‐width graphs

Channel connectivity problem in cognitive radio network (CCP in CRN) is to find a channel assignment for secondary users (SUs) such that underlying graph induced by SUs (potential graph) is connected. Channel connectivity problem in CRNs has been proved to be NP‐complete for general graph and remains NP‐complete even if the underlying potential graph is the tree. Fixed parameter tractability of CCP in CRN has been of research interest because of its practicability. In this work, we have proposed novel problem of fixed parameter tractability for κ ‐CCP of CRN (κ ‐CCP in CRN), ie, whether a given CRN remains connected when any of κ −1 channels are reclaimed by primary users, called κ ‐CCP. This is very crucial to check and design an effective channel assignment algorithm that provides connectivity to SUs on channels reclamation by primary users. To our knowledge, fixed parameter tractability of κ ‐CCP in CRNs has not been studied and becoming useful because of development of 5G if the underlying potential graph has bounded tree‐width and number of channels is parameterized. We address κ ‐CCP in CRN and propose an O (α )^{O (α )}n ^{O (1)} time algorithm if the underlying potential graph is bounded by tree‐width and generates a feasible channel assignment under which given CRN is κ ‐channel connected, where α is the number of channels and n is the number of SUs in CRN. We show that the κ ‐CCP is fixed parameter tractable, when underlying potential graph has bounded tree‐width and number of channels is parameterized. To count the different possible potential solution of κ ‐CCP, we propose a polynomial time algorithm for the corresponding enumeration problem (the number of different feasible channel assignments) E n u m ‐κ ‐CCP on the potential graph with bounded tree‐width when the number of channels is bounded by a constant. Through simulation, we have observed that the feasibility of κ ‐CCP highly depends on the available channels at each SU and number of radio present at each SU.     

无线传感器网络中最小化能量广播算法

在无线传感器网络广播中,为保证所有节点都接收到广播的数据包并调节节点功率以最小化广播总能耗,在Cartigny等人提出的面向相对邻图的广播算法RBOP(relative neighborhood graph broadcast oriented protocol)的基础上,提出了更为节能的增强的面向相对邻图的广播算法ERBOP(enhanced relative neighborhood graph broadcast oriented protocol)。首先在相对邻图上删除较长边得到相对邻图的子图,该子图是连通稀疏图且包含了原图的最小生成树,然后在该子图上构造1-支配的连通支配集,只有支配点才参与数据包转发。仿真显示ERBOP有效节约了能量。     

Index assignment for progressive transmission of full-search vectorquantization

The authors study codeword index assignment to allow for progressive image transmission of fixed rate full-search vector quantization (VQ). They develop three new methods of assigning indices to a vector quantization codebook and formulate these assignments as labels of nodes of a full-search progressive transmission tree. The tree is used to design intermediate codewords for the decoder so that full-search VQ has a successive approximation character. The binary representation for the path through the tree represents the progressive transmission code. The methods of designing the tree that they apply are the generalized Lloyd algorithm, minimum cost perfect matching from optimization theory, and a method of principal component partitioning. Their empirical results show that the final method gives intermediate signal-to-noise ratios (SNRs) that are close to those obtained with tree-structured vector quantization, yet they have higher final SNRs.     

Design of capacity-approaching irregular low-density parity-checkcodes

We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the codes is based on the work of Richardson and Urbanke (see ibid., vol.47, no.2, p.599-618, 2000). Assuming that the underlying communication channel is symmetric, we prove that the probability densities at the message nodes of the graph possess a certain symmetry. Using this symmetry property we then show that, under the assumption of no cycles, the message densities always converge as the number of iterations tends to infinity. Furthermore, we prove a stability condition which implies an upper bound on the fraction of errors that a belief-propagation decoder can correct when applied to a code induced from a bipartite graph with a given degree distribution. Our codes are found by optimizing the degree structure of the underlying graphs. We develop several strategies to perform this optimization. We also present some simulation results for the codes found which show that the performance of the codes is very close to the asymptotic theoretical bounds     

One-to-many multicast restoration based on dynamic core-based selection algorithm in WDM mesh networks

This paper proposes a novel dynamic core-based selection (DCS) algorithm for the multicast restoration in WDM mesh networks. The core-based fault tolerance scheme provides a flexible way to control a number of core nodes with less control overheads for searching the routing path, wavelength assignment (RWA), and restoration paths when fault occurs in the one-to-many multicast domain. Compared with the source-based scheme, core-based schemes are easier to maintain, and specifically scalable in large-scale topologies. In the core-based fault tolerance scheme, k-tuple domination nodes are selected to form a minimum sized vertex subset such that each vertex in the graph is dominated by at least k vertices, where the k is defined as two in this paper. The proposed DCS algorithm is defined as each node in multicast tree session must be directly connected to at least one core node in multicast tree session and also has to be directly connected to at least one core node out of multicast tree session. The primary aim of this work is to provide the scalable and fast local survivability based on the information from core nodes. Simulation results show that the proposed algorithm outperforms the Dual Tree and MRLR algorithms in terms of total hop counts needed for all recovery paths and blocking probability for different network topologies.     

LDPC码的树图法构造

LDPC码译码采用的是BP算法,但由于回路的存在,使译码重复迭代,特别是短长度的回路使LDPC码的性能下降.为此,用树图法分析了LDPC码的回路及其特性,给出了求解回路长度和所经过节点的方法,非常适合于计算机进行求解.同时也用树图的方法来构造LDPC码,可以在树生成的过程中了解其中的回路数目及长度.     

A quantitative comparison of graph-based models for Internettopology

Graphs are commonly used to model the topological structure of internetworks in order to study problems ranging from routing to resource reservation. A variety of graphs are found in the literature, including fixed topologies such as rings or stars, “well-known” topologies such as the ARPAnet, and randomly generated topologies. While many researchers rely upon graphs for analytic and simulation studies, there has been little analysis of the implications of using a particular model or how the graph generation method may affect the results of such studies. Further, the selection of one generation method over another is often arbitrary, since the differences and similarities between methods are not well understood. This paper considers the problem of generating and selecting graphs that reflect the properties of real internetworks. We review generation methods in common use and also propose several new methods. We consider a set of metrics that characterize the graphs produced by a method, and we quantify similarities and differences among several generation methods with respect to these metrics. We also consider the effect of the graph model in the context of a specific problem, namely multicast routing     

A new model for scheduling packet radio networks

Packet radio networks are modeled as arbitrary graphs by most researchers. In this paper we show that an arbitrary graph is an inaccurate model of the radio networks. This is true because there exists a large class of graphs which will not model the radio networks. Radio networks can be modeled accurately by a restricted class of graphs called the planar point graphs. Since the radio networks can accurately be modeled only by a restricted class of graphs, the NP-completeness results for scheduling using an arbitrary graph as the model, do not correctly reflect the complexity of the problem. In this paper we study the broadcast scheduling problem using the restricted class as the model. We show that the problem remains NP-complete even in this restricted domain. We give an O(n log n) algorithm when all the transceivers are located on a line. This revised version was published online in July 2006 with corrections to the Cover Date.     

Covering properties of convolutional codes and associated lattices

The paper describes Markov methods for analyzing the expected and worst case performance of sequence-based methods of quantization. We suppose that the quantization algorithm is dynamic programming, where the current step depends on a vector of path metrics, which we call a metric function. Our principal objective is a concise representation of these metric functions and the possible trajectories of the dynamic programming algorithm. We shall consider quantization of equiprobable binary data using a convolutional code. Here the additive group of the code splits the set of metric functions into a finite collection of subsets. The subsets form the vertices of a directed graph, where edges are labeled by aggregate incremental increases in mean squared error (MSE). Paths in this graph correspond both to trajectories of the Viterbi algorithm and to cosets of the code. For the rate 1/2 convolutional code [1+D², 1+D+D²], this graph has only nine vertices. In this case it is particularly simple to calculate per dimension expected and worst case MSE, and performance is slightly better than the binary [24, 12] Golay code. Our methods also apply to quantization of arbitrary symmetric probability distributions on [0, 1] using convolutional codes. For the uniform distribution on [0, 1], the expected MSE is the second moment of the “Voronoi region” of an infinite-dimensional lattice determined by the convolutional code. It may also be interpreted as an increase in the reliability of a transmission scheme obtained by nonequiprobable signaling. For certain convolutional codes we obtain a formula for expected MSE that depends only on the distribution of differences for a single pair of path metrics     

Comparison of constructions of irregular Gallager codes

The low-density parity check codes whose performance is closest to the Shannon limit are “Gallager codes” based on irregular graphs. We compare alternative methods for constructing these graphs and present two results. First, we find a “super-Poisson” construction which gives a small improvement in empirical performance over a random construction. Second, whereas Gallager codes normally take N² time to encode, we investigate constructions of regular and irregular Gallager codes that allow more rapid encoding and have smaller memory requirements in the encoder. We find that these “fast encoding” Gallager codes have equally good performance     

A tree partitioning dynamic policy for OVSF codes assignment in wideband CDMA

This paper proposes some novel techniques to accommodate users with different rate requirements in a wideband code-division multiple-access system employing orthogonal variable spreading factor codes. Two simple static code assignment strategies are first considered, and an improvement based on multicode assignment. Then the new idea of tree partitioning is introduced and used to devise a dynamic code reassignment algorithm. The behavior of these different techniques is experimentally investigated, in terms of call blocking probability and number of required reassignments. The tree partitioning method exhibits very good performances.     

低复杂度的LDPC码联合编译码构造方法研究

LDPC码因为其具有接近香农限的译码性能和适合高速译码的并行结构,已经成为纠错编码领域的研究热点。LDPC码校验矩阵的构造是基于稀疏的随机图,所以该类码字编码和译码的硬件实现比较复杂。以单位阵的循环移位阵为基本单元,构造LDPC码的校验矩阵,降低了LDPC码在和积算法下的译码复杂度。同时考虑到LDPC码的编码复杂度,给出了一种可以简化编码的结构。针对该方案构造的LDPC码,提出了消除其二分图上的短圈的方法。通过大量的仿真和计算分析,本文比较了这种LDPC码和随机构造的LDPC码在误码率性能,圈长分布以及最小码间距估计上的差异。     

Maximally flexible assignment of orthogonal variable spreading factor codes for multirate traffic

In universal terrestrial radio access (UTRA) systems, orthogonal variable spreading factor (OVSF) codes are used to support different transmission rates for different users. In this paper, we first define the flexibility index to measure the capability of an assignable code set in supporting multirate traffic classes. Based on this index, two single-code assignment schemes, nonrearrangeable and rearrangeable compact assignments, are proposed. Both schemes can offer maximal flexibility for the resulting code tree after each code assignment. We then present an analytical model and derive the call blocking probability, system throughput and fairness index. Analytical and simulation results show that the proposed schemes are efficient, stable and fair.     

On the composition of Tunstall messages

We study the composition of messages in an encoding tree for a Tunstall code, and, more generally, in a tree whose skewness is bounded. For such trees a sort of “law of large numbers” holds true; actually, we provide a direct and converse coding theorem for variable-length to block length source codes, when a vanishing error probability is allowed