15745921
Wireless networks and random geometric graphs
In this paper, mobile ad-hoc networks are studied. Chen and Jia (2001) proposed a routing algorithm by utilizing multiple communication channels and localizing the routing information (routing tables) for mobile stations within the wireless network. The routing algorithm relies on a spanning tree of the underlying network. It is proven that both the construction of the spanning tree and the routing algorithm are efficient. The routing algorithm is also reliable because of the frequent update of the spanning tree which the routing scheme is based on. The underlying network is a random geometric graph G(A,n) formed on a set of uniformly randomly located points in the unit disk, in which two vertices are adjacent if and only if their Euclidean distance is at most A.
40163188
Triple Loop Networks with Minimal Transmission Delay
A multiloop network is a Cayley digraph of the additive group ℤm of integers modulo m generated by a set A of k ≥ 2 "steps". Because of their application to the computer network design, multiloop networks have been studied extensively. Given an integer d ≥ 2 and a real number r > 1, let m(d,3) be the maximum size of a triple loop network with transmission delay (diameter) less than or equal to d, and let m*(r,3) be the maximum size of a triple loop network with average transmission delay less than or equal to r. In this paper, the following lower bounds are proved: which improve earlier lower bounds by Jia and Aguilo, Fiol and Garcia.
41488878
On a Network Sensing Problem
Live traffic flow information can help improve the efficiency of a communication network. There are many ways available to monitor the traffic flow of a network. In this paper, we propose a very efficient monitoring strategy. This strategy not only reduces the number of nodes to be monitored but also determines the complete traffic information of the entire network using the information from the monitored nodes. The strategy is optimal for monitoring a network because it reduces the number of monitored nodes to a minimum. Fast algorithms are also presented in this paper to compute the traffic information for the entire network based on the information collected from the monitored nodes. The monitoring scheme discussed in this paper can be applied to the internet, telecommunication networks, wireless ad hoc networks, large scale multiprocessor computing systems, and other information systems where the transmission of information needs to be monitored.
2884321
Some remarks on minimal bases and maximal nonbases of integers
Abstract In this note, we generalize the concepts of minimal bases and maximal nonbases for integers, and prove some existence theorems for the generalized minimal bases and maximal nonbases, which generalize some results of Stohr, Deza and Erdos, and Nathanson.
19271257
Extremal Cayley Digraphs of Finite Cyclic Groups
Let $\cay(m,A)$ denote the Cayley digraph on ${\bf Z}_m$ generated by $A$, where ${\bf Z}_m$ is the cyclic group of residues modulo $m$. Let $r(m,A)$ denote the average distance of $\cay(m,A)$. For any $r\ge1$ and $k\ge1$ define $m^*(r,k)$ as the largest positive integer $m$ such that the average distance of the Cayley digraph $\hbox{Cay}(m,A)$ is at most $r$ for some set $A$ with $k$ elements. In this paper, an asymptotic formula for $m^*(r,2)$ is proved and a lower bound for $m^*(r,k)$ is also obtained for $k\ge3$. Applications to the construction of optimal distributed loop networks is discussed in this paper. A lower bound of the average order of subsets for asymptotic bases in number theory is proved using the main theorem of this paper.
20605726
Extremal Problems in the Construction of Distributed Loop Networks
Let $G(N, A)$ be the Cayley digraph associated with ${\bf Z}/(N)$ and $A$, where $N$ is a positive integer and $A$ is a subset of $\{1, 2, ..., N - 1\}$. Let $N(d, k)$ be the maximum $N$ such that the diameter of $G(N, A)$ is less than or equal to $d$ for some $A = \{a_{1}, a_{2},\ldots, a_{k}\}$ with $1 = a_{1}, < a_{2} < \cdots < a_{k}. An exact formula for $N(d, 2)$ is given, and $N(d, k)$ is estimated for $k \geq 3$. These results provide new bounds for minimal diameter in the construction of loop networks. A relation between this problem and the postage stamp problem in additive number theory is established to enhance the study of these problems.
16675541
The GAPLA: a globally asynchronous locally synchronous FPGA architecture
This paper proposes GAPLA: a globally asynchronous locally synchronous programmable logic array architecture. The whole FPGA area is divided into locally synchronous blocks wrapped with asynchronous I/O interfaces. Data communications between synchronous blocks are controlled by 2-phase handshaking signals. The size and shape of each locally synchronous block are programmable so that different modules in a design can be effectively implemented. Each block could run at higher speed because only the fast local interconnections are used. Experimental results show an up to 28% performance improvement compared to the conventional FPGAs with small area overhead (around 2%).
13944177
A pragmatic approach to formalizing object-oriented modeling and development
Despite recent developments in formal methods, these methods have yet to enter the mainstream of the software industry. We first examine the pragmatic obstacles to making formal methods practical and usable. Then we present a pragmatic approach to integrate a popular object oriented modeling notation UML and a popular formal notation Z. Our approach is distinctive in its emphasis on overcoming the practical obstacles. We also present a light weight supporting tool for our approach. A prototype of the supporting tool is completed. It allows us to demonstrate the feasibility and capability of our approach.
26178565
A Design Methodology for Self-Timed Event Logic Pipelines
16011778
A Uniform System for Publishing and Maintaining XML Data
XML has become the prime standard for data exchange on the Web. To exchange data residing in Databases, one needs to publish it in XML. Data publishing is often done with a predefined “schema.” The chapter proposes a new approach for schema-directed publishing of relational data in XML, based on the novel notion of attribute transformation grammars (ATGs). ATGs provide guidance on how to define views conforming to target schemas (DTDs), and automatically ensure schema conformance. The chapter also develops an incremental algorithm for maintaining XML views produced by ATGs, based on new incremental computation techniques that capitalize on the hierarchical structure of XML data and unique features of the ATGs. Taking real-life data from Gene Ontology (GO), this chapter also demonstrates how this system can efficiently publish the GO data in XML with respect to a predefined recursive DTD, and how it incrementally updates the target XML data in response to changes to the underlying GO database.
6166247
Virtual backbone construction in multihop ad hoc wireless networks
Summary Recent research points out that the flooding mechanism for topology update or route request in existing ad hoc routing protocols greatly degrades the network capacity. If we restrict the broadcast of control packets within a small subset of hosts in the network, the protocol overhead can be substantially reduced. This motivates our research of constructing a virtual backbone by computing a connected dominating set (CDS) in unit-disk graphs. In this paper, we propose two distributed algorithms to approximate a minimum CDS. These algorithms take linear time. Their performance is verified by a complete theoretical analysis. Copyright # 2006 John Wiley & Sons, Ltd.