OpenRaiser/Intern-Atlas huggingface dataset:
Interference Mitigation Through Limited Receiver Cooperation
Venue: arXiv cs.IT 2009
Year: 2009

Interference is a major issue limiting the performance in wireless networks. Cooperation among receivers can help mitigate interference by forming distributed MIMO systems. The rate at which receivers cooperate, however, is limited in most scenarios. How much interference can one bit of receiver cooperation mitigate? In this paper, we study the two-user Gaussian interference channel with conferencing decoders to answer this question in a simple setting. We identify two regions regarding the gain from receiver cooperation: linear and saturation regions. In the linear region receiver cooperation is efficient and provides a degrees-of-freedom gain, which is either one cooperation bit buys one more bit or two cooperation bits buy one more bit until saturation. In the saturation region receiver cooperation is inefficient and provides a power gain, which is at most a constant regardless of the rate at which receivers cooperate. The conclusion is drawn from the characterization of capacity region to within two bits. The proposed strategy consists of two parts: (1) the transmission scheme, where superposition encoding with a simple power split is employed, and (2) the cooperative protocol, where one receiver quantize-bin-and-forwards its received signal, and the other after receiving the side information decode-bin-and-forwards its received signal.
A scientific understanding of network designing
Venue: arXiv cs.NI 2009
Year: 2009

As the Internet becomes severely overburdened with exponentially growing traffic demand, it becomes a general belief that a new generation data network is in urgent need today. However, standing at this crossroad, we find that we are in a situation that lacks a theory of network designing. This issue becomes even more serious as the recent progress of network measurement and modeling challenges the foundation of network research in the past decades. This paper tries to set up a scientific foundation for network designing by formalizing it as a multi-objective optimization process and quantifying the way different designing choices independently and collectively influence these objectives. A cartesian coordinate system is introduced to map the effect of each designing scheme to a coordinate. We investigated the achievable area of the network designing space and proved some boundary conditions. It is shown that different kind of networks display different shapes of achievable areas in the cartesian coordinate and exhibit different abilities to achieve cost-effective and scalable designing. In particular, we found that the philosophy underlying current empirical network designing and engineering fails to meet the cost-effective and evolvable requirements of network designing. We demonstrated that the efficient routing combined with effective betweenness based link bandwidth allocation scheme is a cost-effective and scalable design for BA-like scale-free networks, whereas if other designing choices cannot be determined beforehand, ER network is a markedly good candidate for cost-effective and scalable design.
Circular Languages Generated by Complete Splicing Systems and Pure Unitary Languages
Venue: arXiv cs.FL 2009
Year: 2009

Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. Some unanswered questions are related to the computational power of such systems, and finding a characterization of the class of circular languages generated by circular splicing systems is still an open problem. In this paper we solve this problem for complete systems, which are special finite circular splicing systems. We show that a circular language L is generated by a complete system if and only if the set Lin(L) of all words corresponding to L is a pure unitary language generated by a set closed under the conjugacy relation. The class of pure unitary languages was introduced by A. Ehrenfeucht, D. Haussler, G. Rozenberg in 1983, as a subclass of the class of context-free languages, together with a characterization of regular pure unitary languages by means of a decidable property. As a direct consequence, we characterize (regular) circular languages generated by complete systems. We can also decide whether the language generated by a complete system is regular. Finally, we point out that complete systems have the same computational power as finite simple systems, an easy type of circular splicing system defined in the literature from the very beginning, when only one rule is allowed. From our results on complete systems, it follows that finite simple systems generate a class of context-free languages containing non-regular languages, showing the incorrectness of a longstanding result on simple systems.
Distributed Coalition Formation Games for Secure Wireless Transmission
Venue: arXiv cs.IT 2009
Year: 2009

Cooperation among wireless nodes has been recently proposed for improving the physical layer (PHY) security of wireless transmission in the presence of multiple eavesdroppers. While existing PHY security literature answered the question ``what are the link-level secrecy rate gains from cooperation?'', this paper attempts to answer the question of ``how to achieve those gains in a practical decentralized wireless network and in the presence of a cost for information exchange?''. For this purpose, we model the PHY security cooperation problem as a coalitional game with non-transferable utility and propose a distributed algorithm for coalition formation. Through the proposed algorithm, the wireless users can cooperate and self-organize into disjoint independent coalitions, while maximizing their secrecy rate taking into account the security costs during information exchange. We analyze the resulting coalitional structures for both decode-and-forward and amplify-and-forward cooperation and study how the users can adapt the network topology to environmental changes such as mobility. Through simulations, we assess the performance of the proposed algorithm and show that, by coalition formation using decode-and-forward, the average secrecy rate per user is increased of up to 25.3 % and 24.4 % (for a network with 45 users) relative to the non-cooperative and amplify-and-forward cases, respectively.
Boltzmann Samplers for Colored Combinatorial Objects
Venue: arXiv cs.DM 2009
Year: 2009

In this paper, we give a general framework for the Boltzmann generation of colored objects belonging to combinatorial constructible classes. We propose an intuitive notion called profiled objects which allows the sampling of size-colored objects (and also of k-colored objects) although the corresponding class cannot be described by an analytic ordinary generating function.
Global communications in multiprocessor simulations of flames
Venue: arXiv cs.DC 2009
Year: 2009

In this paper we investigate performance of global communications in a particular parallel code. The code simulates dynamics of expansion of premixed spherical flames using an asymptotic model of Sivashinsky type and a spectral numerical algorithm. As a result, the code heavily relies on global all-to-all interprocessor communications implementing transposition of the distributed data array in which numerical solution to the problem is stored. This global data interdependence makes interprocessor connectivity of the HPC system as important as the floating-point power of the processors of which the system is built. Our experiments show that efficient numerical simulation of this particular model, with global data interdependence, on modern HPC systems is possible. Prospects of performance of more sophisticated models of flame dynamics are analysed as well.
Computation Speed of the F.A.S.T. Model
Venue: arXiv cs.MA 2009
Year: 2009

The F.A.S.T. model for microscopic simulation of pedestrians was formulated with the idea of parallelizability and small computation times in general in mind, but so far it was never demonstrated, if it can in fact be implemented efficiently for execution on a multi-core or multi-CPU system. In this contribution results are given on computation times for the F.A.S.T. model on an eight-core PC.
Citation Environment of Angewandte Chemie
Venue: arXiv cs.DL 2009
Year: 2009

Recently, aggregated journal-journal citation networks were made accessible from the perspective of each journal included in the Science Citation Index see (http://www.leydesdorff.net/). The local matrices can be used to inspect the relevant citation environment of a journal using statistical analysis and visualization techniques from social network analysis. The inspection gives an answer to the question what the local impact of this and other journals in the environment is. In this study the citation environment of Angewandte Chemie was analysed. Angewandte Chemie is one of the prime chemistry journals in the world. Its environment was compared with that of the Journal of the American Chemical Society. The results of the environment analyses give a detailed insight into the field-embeddedness of Angewandte Chemie. The impacts of the German and international editions of this journal are compared.
A Comparison between the China Scientific and Technical Papers and Citations Database and the Science Citation Index in terms of journal hierarchies and inter-journal citation relations
Venue: arXiv cs.DL 2009
Year: 2009

The journal structure in the China Scientific and Technical Papers and Citations Database (CSTPCD) is analysed from three perspectives: the database level, the specialty level and the institutional level (i.e., university journals versus journals issued by the Chinese Academy of Sciences). The results are compared with those for (Chinese) journals included in the Science Citation Index. The frequency of journal-journal citation relations in the CSTPCD is an order of magnitude lower than in the SCI. Chinese journals, especially high-quality journals, prefer to cite international journals rather than domestic ones. However, Chinese journals do not get an equivalent reception from their international counterparts. The international visibility of Chinese journals is low, but varies among fields of science. Journals of the Chinese Academy of Sciences (CAS) have a better reception in the international scientific community than university journals.
An Inverse Method for Policy-Iteration Based Algorithms
Venue: arXiv cs.DM 2009
Year: 2009

We present an extension of two policy-iteration based algorithms on weighted graphs (viz., Markov Decision Problems and Max-Plus Algebras). This extension allows us to solve the following inverse problem: considering the weights of the graph to be unknown constants or parameters, we suppose that a reference instantiation of those weights is given, and we aim at computing a constraint on the parameters under which an optimal policy for the reference instantiation is still optimal. The original algorithm is thus guaranteed to behave well around the reference instantiation, which provides us with some criteria of robustness. We present an application of both methods to simple examples. A prototype implementation has been done.
Pipelined Encoding for Deterministic and Noisy Relay Networks
Venue: arXiv cs.IT 2009
Year: 2009

Recent coding strategies for deterministic and noisy relay networks are related to the pipelining of block Markov encoding. For deterministic networks, it is shown that pipelined encoding improves encoding delay, as opposed to end-to-end delay. For noisy networks, it is observed that decode-and-forward exhibits good rate scaling when the signal-to-noise ratio (SNR) increases.
Evolutionary estimation of a Coupled Markov Chain credit risk model
Venue: arXiv cs.NE 2009
Year: 2009

There exists a range of different models for estimating and simulating credit risk transitions to optimally manage credit risk portfolios and products. In this chapter we present a Coupled Markov Chain approach to model rating transitions and thereby default probabilities of companies. As the likelihood of the model turns out to be a non-convex function of the parameters to be estimated, we apply heuristics to find the ML estimators. To this extent, we outline the model and its likelihood function, and present both a Particle Swarm Optimization algorithm, as well as an Evolutionary Optimization algorithm to maximize the likelihood function. Numerical results are shown which suggest a further application of evolutionary optimization techniques for credit risk management.
Continuous Verification of Large Embedded Software using SMT-Based Bounded Model Checking
Venue: arXiv cs.SE 2009
Year: 2009

The complexity of software in embedded systems has increased significantly over the last years so that software verification now plays an important role in ensuring the overall product quality. In this context, SAT-based bounded model checking has been successfully applied to discover subtle errors, but for larger applications, it often suffers from the state space explosion problem. This paper describes a new approach called continuous verification to detect design errors as quickly as possible by looking at the Software Configuration Management (SCM) system and by combining dynamic and static verification to reduce the state space to be explored. We also give a set of encodings that provide accurate support for program verification and use different background theories in order to improve scalability and precision in a completely automatic way. A case study from the telecommunications domain shows that the proposed approach improves the error-detection capability and reduces the overall verification time by up to 50%.
Delay Bounds for Networks with Heavy-Tailed and Self-Similar Traffic
Venue: arXiv cs.NI 2009
Year: 2009

We provide upper bounds on the end-to-end backlog and delay in a network with heavy-tailed and self-similar traffic. The analysis follows a network calculus approach where traffic is characterized by envelope functions and service is described by service curves. A key contribution of this paper is the derivation of a probabilistic sample path bound for heavy-tailed self-similar arrival processes, which is enabled by a suitable envelope characterization, referred to as `htss envelope'. We derive a heavy-tailed service curve for an entire network path when the service at each node on the path is characterized by heavy-tailed service curves. We obtain backlog and delay bounds for traffic that is characterized by an htss envelope and receives service given by a heavy-tailed service curve. The derived performance bounds are non-asymptotic in that they do not assume a steady-state, large buffer, or many sources regime. We also explore the scale of growth of delays as a function of the length of the path. The appendix contains an analysis for self-similar traffic with a Gaussian tail distribution.
Q-ESP: a QoS-compliant Security Protocol to enrich IPSec Framework
Venue: arXiv cs.CR 2009
Year: 2009

IPSec is a protocol that allows to make secure connections between branch offices and allows secure VPN accesses. However, the efforts to improve IPSec are still under way; one aspect of this improvement is to take Quality of Service (QoS) requirements into account. QoS is the ability of the network to provide a service at an assured service level while optimizing the global usage of network resources. The QoS level that a flow receives depends on a six-bit identifier in the IP header; the so-called Differentiated Services code point (DSCP). Basically, Multi-Field classifiers classify a packet by inspecting IP/TCP headers, to decide how the packet should be processed. The current IPSec standard does hardly offer any guidance to do this, because the existing IPSec ESP security protocol hides much of this information in its encrypted payloads, preventing network control devices such as routers and switches from utilizing this information in performing classification appropriately. To solve this problem, we propose a QoS-friendly Encapsulated Security Payload (Q-ESP) as a new IPSec security protocol that provides both security and QoS supports. We also present our NetBSD kernel-based implementation as well as our evaluation results of Q-ESP.
About a new splitting for the algorithmic study of the tilings $\{p,q\}$ of the hyperbolic plane when $q$ is odd
Venue: arXiv cs.CG 2009
Year: 2009

In this paper, we remind previous results about the tilings $\{p,q\}$ of the hyperbolic plane. We introduce two new ways to split the hyperbolic plane in order to algorithmically construct the tilings $\{p,q\}$ when $q$ is odd.
Efficient Local Unfolding with Ancestor Stacks
Venue: arXiv cs.PL 2009
Year: 2009

The most successful unfolding rules used nowadays in the partial evaluation of logic programs are based on well quasi orders (wqo) applied over (covering) ancestors, i.e., a subsequence of the atoms selected during a derivation. Ancestor (sub)sequences are used to increase the specialization power of unfolding while still guaranteeing termination and also to reduce the number of atoms for which the wqo has to be checked. Unfortunately, maintaining the structure of the ancestor relation during unfolding introduces significant overhead. We propose an efficient, practical local unfolding rule based on the notion of covering ancestors which can be used in combination with a wqo and allows a stack-based implementation without losing any opportunities for specialization. Using our technique, certain non-leftmost unfoldings are allowed as long as local unfolding is performed, i.e., we cover depth-first strategies.
On convexification of polygons by pops
Venue: arXiv cs.CG 2009
Year: 2009

Given a polygon $P$ in the plane, a {\em pop} operation is the reflection of a vertex with respect to the line through its adjacent vertices. We define a family of alternating polygons, and show that any polygon from this family cannot be convexified by pop operations. This family contains simple, as well as non-simple (i.e., self-intersecting) polygons, as desired. We thereby answer in the negative an open problem posed by Demaine and O'Rourke \cite[Open Problem 5.3]{DO07}.
From Self-Interpreters to Normalization by Evaluation
Venue: arXiv cs.PL 2009
Year: 2009

We characterize normalization by evaluation as the composition of a self-interpreter with a self-reducer using a special representation scheme, in the sense of Mogensen (1992). We do so by deriving in a systematic way an untyped normalization by evaluation algorithm from a standard interpreter for the ?-calculus. The derived algorithm is not novel and indeed other published algorithms may be obtained in the same manner through appropriate adaptations to the representation scheme.
Splitting Algorithms for Fast Relay Selection: Generalizations, Analysis, and a Unified View
Venue: arXiv cs.NI 2009
Year: 2009

Relay selection for cooperative communications promises significant performance improvements, and is, therefore, attracting considerable attention. While several criteria have been proposed for selecting one or more relays, distributed mechanisms that perform the selection have received relatively less attention. In this paper, we develop a novel, yet simple, asymptotic analysis of a splitting-based multiple access selection algorithm to find the single best relay. The analysis leads to simpler and alternate expressions for the average number of slots required to find the best user. By introducing a new `contention load' parameter, the analysis shows that the parameter settings used in the existing literature can be improved upon. New and simple bounds are also derived. Furthermore, we propose a new algorithm that addresses the general problem of selecting the best $Q \ge 1$ relays, and analyze and optimize it. Even for a large number of relays, the algorithm selects the best two relays within 4.406 slots and the best three within 6.491 slots, on average. We also propose a new and simple scheme for the practically relevant case of discrete metrics. Altogether, our results develop a unifying perspective about the general problem of distributed selection in cooperative systems and several other multi-node systems.
Bigraphical models for protein and membrane interactions
Venue: arXiv cs.CE 2009
Year: 2009

We present a bigraphical framework suited for modeling biological systems both at protein level and at membrane level. We characterize formally bigraphs corresponding to biologically meaningful systems, and bigraphic rewriting rules representing biologically admissible interactions. At the protein level, these bigraphic reactive systems correspond exactly to systems of kappa-calculus. Membrane-level interactions are represented by just two general rules, whose application can be triggered by protein-level interactions in a well-deïned and precise way. This framework can be used to compare and merge models at different abstraction levels; in particular, higher-level (e.g. mobility) activities can be given a formal biological justification in terms of low-level (i.e., protein) interactions. As examples, we formalize in our framework the vesiculation and the phagocytosis processes.
On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence
Venue: arXiv cs.CC 2009
Year: 2009

It is shown that the length of the algorithmic minimal sufficient statistic of a binary string x, either in a representation of a finite set, computable semimeasure, or a computable function, has a length larger than the computational depth of x, and can solve the Halting problem for all programs with length shorter than the m-depth of x. It is also shown that there are strings for which the algorithmic minimal sufficient statistics can contain a substantial amount of information that is not Halting information. The weak sufficient statistic is introduced, and it is shown that a minimal weak sufficient statistic for x is equivalent to a minimal typical model of x, and to the Halting problem for all strings shorter than the BB-depth of x.
Cooperative Relaying with State Available Non-Causally at the Relay
Venue: arXiv cs.IT 2009
Year: 2009

We consider a three-terminal state-dependent relay channel with the channel state noncausally available at only the relay. Such a model may be useful for designing cooperative wireless networks with some terminals equipped with cognition capabilities, i.e., the relay in our setup. In the discrete memoryless (DM) case, we establish lower and upper bounds on channel capacity. The lower bound is obtained by a coding scheme at the relay that uses a combination of codeword splitting, Gel'fand-Pinsker binning, and decode-and-forward relaying. The upper bound improves upon that obtained by assuming that the channel state is available at the source, the relay, and the destination. For the Gaussian case, we also derive lower and upper bounds on the capacity. The lower bound is obtained by a coding scheme at the relay that uses a combination of codeword splitting, generalized dirty paper coding, and decode-and-forward relaying; the upper bound is also better than that obtained by assuming that the channel state is available at the source, the relay, and the destination. In the case of degraded Gaussian channels, the lower bound meets with the upper bound for some special cases, and, so, the capacity is obtained for these cases. Furthermore, in the Gaussian case, we also extend the results to the case in which the relay operates in a half-duplex mode.