A digital neural network approach is presented for the multilayer channel routing problem with the objective of crosstalk minimization in this paper. As VLSI fabrication technology advances, the reduction of crosstalk between interconnection wires on a chip has gained important consideration in VLSI design, because of the closer interwire spacing and the circuit operation at higher frequencies. Our neural network is composed of N M L digital neurons with one-bit output and seven-bit input for the N-net-M-track-2L-layer problem using a set of integer parameters, which is greatly suitable for the implementaion on digital technology. The digital neural network directly seeks a routing solution of satisfying the routing constraint and the crosstalk constraint simultaneously. The heuristic methods are effectively introduced to improve the convergence property. The performance is evaluated through solving 10 benchmark problems including Deutsch difficult example in 2-10 layers. Among the existing neural networks, the digital neural network first achieves the lower bound solution in terms of the number of tracks in any instance. Through extensive simulation runs, it provides the best maximum crosstalks of nets for valid routing solutions of the benchmark problems in multilayer channels.

A neural network approach called the "Gradual Neural Network (GNN)" for the time slot assignment problem in the TDM multicast switching system is presented in this paper. The goal of this NP-complete problem is to find an assignment of packet transmission requests into a minimum number of time slots. A packet can be transmitted from one source to several destinations simultaneously by its replication. A time slot represents a switching configuration of the system with unit time for each packet transmission through an I/O line. The GNN consists of the binary neural network and the gradual expansion scheme. The binary neural network satisfies the constraints imposed on the system by solving the motion equation, whereas the gradual expansion scheme minimizes the number of required time slots by gradually expanding activated neurons. The performance is evaluated through simulations in practical size systems, where the GNN finds far better solutions than the best existing altorithm.

A constraint resolution scheme in the Hopfield-type neural network named "Neuron Filter" is presented for efficiently solving combinatorial optimization problems. The neuron filter produces an output that satisfies the constraints of the problem as best as possible according to both neuron inputs and outputs. This paper defines the neuron filter and shows its introduction into existing neural networks for N-queens problems and FPGA board-level routing problems. The performance is evaluated through simulations where the results show that our neuron filter improves the searching capability of the neural network with the shorter computation time.

Lots of revocable group signature schemes have been proposed so far. In one type of revocable schemes, signing and/or verifying algorithms have O(N) or O(R) complexity, where N is the group size and R is the number of revoked members. On the other hand, in Camenisch-Lysyanskaya scheme and the followers, signing and verifying algorithms have O(1) complexity. However, before signing, the updates of the secret key are required. The complexity is O(R) in the worst case. In this paper, we propose a revocable scheme with signing and verifying of O(1) complexity, where any update of secret key is not required. The compensation is the long public key of O(N). In addition, we extend it to the scheme with O()-size public key, where signing and verifying have constant extra costs.

A group signature scheme allows a group member to anonymously sign a message on behalf of the group. One of the important issues is the member revocation, and lots of revocable schemes have been proposed so far. A scheme recently proposed by Libert et al. achieves that O(1) or O(log N) efficiency of communication and computation except for the revocation list size (also the revocation cost), for the total number of members N and the number of revoked members R. However, since a signature is required for each subset separated from the set of non-revoked members, the size is about 900R Bytes in the 128-bit security. In the case of R=100,000, it amounts to about 80MB. In this paper, we extend the scheme to reduce the revocation list (also the revocation cost), by accumulating T subsets, which is signed for the revocation list. The revocation list size is reduced by 1/T. Unfortunately, the public key size, membership certificate size and the cost of a witness computation needed for signing increase related to T.

Wireless mesh networks have been extensively studied as expandable, flexible, and inexpensive access networks to the Internet. This paper focuses on one composed of multiple access points (APs) connected through multihop wireless communications mainly by the wireless distribution system (WDS). For scalability, the proper partition of APs into multiple WDS clusters is essential, because the number of APs in one cluster is limited due to the increasing radio interference and control packets. In this paper, we formulate this WDS clustering problem and prove the NP-completeness of its decision version through reduction from a known NP-complete problem. Then, we propose its heuristic algorithm, using a greedy method and a variable depth search method, to satisfy the complex constraints while optimizing the cost function. We verify the effectiveness of our algorithm through extensive simulations, where the results confirm its superiority to the existing algorithm in terms of throughput.

The spaces between words and paragraphs are popular places for embedding data in data hiding techniques for text documents. Due to the low redundancy in text documents, the payload is limited to be small. As each bit of data is independently inserted into specific spaces in conventional methods, a malicious party may be able to modify the data without causing serious visible distortions. In this paper, we regard a collection of space lengths as a one-dimensional feature vector and embed watermark into its frequency components. To keep the secrecy of the embedded information, a random permutation and dither modulation are introduced in the operation. Furthermore, robustness against additive noise is enhanced by controlling the payload. In the proposed method, through experiments, we evaluated the trade-off among payload, distortion, and robustness.

As a flexible and cost-efficient scalable Internet access network, we studied architectures, protocols, and design optimizations of the Wireless Internet-access Mesh NETwork (WIMNET). WIMNET is composed of multiple access points (APs) connected through multihop wireless communications on IEEE 802.11 standards. The increasing popularity of real-time applications such as IP-phones and IP-TV means that they should be supported in WIMNET. However, the contention resolution mechanism using a random backoff-time in the CSMA/CA protocol of 802.11 standards is not sufficient for handling real-time traffic in multihop wireless communications. In this paper, we propose a Fixed Backoff-time Switching (FBS) method for the CSMA/CA protocol to improve the real-time traffic performance in WIMNET by giving the necessary activation chances to each link. We implement our proposal on the QualNet simulator, and verify its effectiveness through simulations on three network topologies with four scenarios.

A novel combinatorial optimization algorithm called 2-stage discrete optimization method (2DOM) is proposed for the largest common subgraph problem (LCSP) in this paper. Given two graphs G=(V1, E1) and H=(V2, E2), the goal of LCSP is to find a subgraph G'=(V1', E1') of G and a subgraph H'=(V2', E2') of H such that G' and H' are not only isomorphic to each other but also their number of edges is maximized. The two graphs G' and H' are isomorphic when |V1'|=|V2'| and |E1'|=|E2'|, and there exists one-to-one vertex correspondence f: V1' V2' such that {u, v} E1' if and only if{f(u), f(v)} E2'. LCSP is known to be NP-complete in general. The 2DOM consists of a construction stage and a refinement stage to achieve the high solution quality and the short computation time for large size difficult combinatorial optimization problems. The construction stage creates a feasible initial solution with considerable quality, based on a greedy heuristic method. The refinement stage improves it keeping the feasibility, based on a random discrete descent method. The performance is evaluated by solving two types of randomly generated 1200 LCSP instances with a maximum of 500 vertices for G and 1000 vertices for H. The simulation result shows the superiority of 2DOM to the simulated annealing in terms of the solution quality and the computation time.

As a flexible, cost effective solution for a large-scale access network to the Internet, we have studied the design optimization of the Wireless Internet-access Mesh NETwork (WIMNET). WIMNET consists of multiple access points (APs) that have wireless links between them mainly on the wireless distribution system (WDS). In WIMNET, the links around the Internet gateway can be bottlenecks because every packet passes through it after multihop link activations. Besides, the link quality may be degraded by obstacles in indoor environments. Thus, the proper allocation of APs is essential in WIMNET, so that the communication quality should be ensured while the installation and management cost be minimized. In this paper, we formulate this AP allocation problem for indoor environments in WIMNET with the proof of the NP-completeness of its decision version. Then, we present its two-stage heuristic algorithm composed of the initial greedy allocation and the iterative improvement. The effectiveness of our proposal is verified through extensive simulations in three indoor environments.

In conventional spread spectrum (SS) watermarking schemes, random sequences are used for the modulation of watermark information. However, because of the mutual interference among those sequences, it requires complicated removal operation to improve the performance. In this paper, we propose an efficient spread spectrum watermarking scheme by introducing the orthogonal frequency divisiion multiplexing (OFDM) technique at the modulation of watermark information. The SS sequences in the proposed method are the DCT basic vectors modulated by a pseudo-random number (PN) sequence. We investigate the SS-based method considering the host interference at the blind detection scenario and analyze the noise caused by attacks. Because every operation is invertible, the quantization index modulation (QIM)-based method is applicable for the OFDM modulated signals. We also consider the property of watermark extracting operation in SS-based and QIM-based method and formalize their models of noisy channel in order to employ an error correcting code. The performance of their methods with error correcting code is numerically evaluated under the constraints of same distortion level in watermarked content. The experimental results indicated a criteria for the selection of SS-based and QIM-based methods for given content, which is determined by the amount of host interference. In case that the host interference is 0.8 times smaller than a watermark signal, the SS-based method is suitable. When it is 1.0 times larger, the QIM-based method should be selected.

The study of universal detector for fingerprinting code is strongly dependent on the design of scoring function. The optimal detector is known as MAP detector that calculates an optimal correlation score for a given single user's codeword. However, the knowledge about the number of colluders and their collusion strategy are inevitable. In this paper, we propose a new scoring function that equalizes the bias between symbols of codeword, which is called bias equalizer. We further investigate an efficient scoring function based on the bias equalizer under the relaxed marking assumption such that white Gaussian noise is added to a pirated codeword. The performance is compared with the MAP detector as well as some state-of-the-art scoring functions.

Homemade cooking plays a key role for a healthy and cost-efficient life. Unfortunately, preparing multiple dishes is generally time-consuming. In this paper, an algorithm is proposed to minimize the cooking time by scheduling the cooking-step of multiple dishes. The cooking procedure of a dish is divided into a sequence of six types of cooking-steps to consider the constraints in cooks and cooking utensils in a kitchen. A cooking model is presented to optimize the cooking-step schedule and estimate the cooking time for a given starting order of dishes under various constraints of cooks and utensils. Then, a high-quality schedule is sought by repeating the generation of a new order and the model application based on exhaustive search and simulated annealing. Our simulation results and cooking experiments confirm the effectiveness of our proposal.

To enhance user privacy, anonymous credential systems allow the user to convince a verifier of the possession of a certificate issued by the issuing authority anonymously. In the systems, the user can prove relations on his/her attributes embedded into the certificate. Previously, a pairing-based anonymous credential system with constant-size proofs in the number of attributes of the user was proposed. This system supports the proofs of the inner product relations on attributes, and thus can handle the complex logical relations on attributes as the CNF and DNF formulas. However this system suffers from the computational cost: The proof generation needs exponentiations depending on the number of the literals in OR relations. In this paper, we propose a pairing-based anonymous credential system with the constant-size proofs for CNF formulas and the more efficient proof generation. In the proposed system, the proof generation needs only multiplications depending on the number of literals, and thus it is more efficient than the previously proposed system. The key of our construction is to use an extended accumulator, by which we can verify that multiple attributes are included in multiple sets, all at once. This leads to the verification of CNF formulas on attributes. Since the accumulator is mainly calculated by multiplications, we achieve the better computational costs.

Currently, the IEEE 802.11n wireless local-area network (WLAN) has been extensively deployed world-wide. For the efficient channel assignment to access-points (APs) from the limited number of partially overlapping channels (POCs) at 2.4GHz band, we have studied the throughput drop estimation model for concurrently communicating links using the channel bonding (CB). However, non-CB links should be used in dense WLANs, since the CB links often reduce the transmission capacity due to high interferences from other links. In this paper, we examine the throughput drop estimation model for concurrently communicating links without using the CB in 802.11n WLAN, and its application to the POC assignment to the APs. First, we verify the model accuracy through experiments in two network fields. The results show that the average error is 9.946% and 6.285% for the high and low interference case respectively. Then, we verify the effectiveness of the POC assignment to the APs using the model through simulations and experiments. The results show that the model improves the smallest throughput of a host by 22.195% and the total throughput of all the hosts by 22.196% on average in simulations for three large topologies, and the total throughput by 12.89% on average in experiments for two small topologies.

A neural network of massively interconnected digital neurons is presented for the total coloring problem in this paper. Given a graph G (V, E), the goal of this NP-complete problem is to find a color assignment on the vertices in V and the edges in E with the minimum number of colors such that no adjacent or incident pair of elements in V and E receives the same color. A graph coloring is a basic combinatorial optimization problem for a variety of practical applications. The neural network consists of (N+M) L neurons for the N-vertex-M-edge-L-color problem. Using digital neurons of binary outputs and range-limited non-negative integer inputs with a set of integer parameters, our digital neural network is greatly suitable for the implementation on digital circuits. The performance is evaluated through simulations in random graphs with the lower bounds on the number of colors. With a help of heuristic methods, the digital neural network of up to 530, 656 neurons always finds a solution in the NP-complete problem within a constant number of iteration steps on the synchronous parallel computation.

This paper presents a binary neural network approach for link activation problems in multihop radio networks. The goal of the NP-complete problems is to find a conflict-free link activation schedule with the minimum number of time slots for specified communication requirements. The neural network is composed of NM binary neurons for scheduling N links in M time slots. The energy functions and the motion equations are newly defined with heuristic methods. The simulation results through 14 instances with up to 419 links show that the neural network not only surpasses the best existing neural network in terms of the convergence rate and the computation time, but also can solve large scale instances within a constant number of iteration steps.

A novel combinatorial optimization algorithm called "Gradual neural network (GNN)" is presented for NP-complete broadcast scheduling problems in packet radio (PR) networks. A PR network provides data communications services to a set of geographically distributed nodes through a common radio channel. A time division multiple access (TDMA) protocol is adopted for conflict-free communications, where packets are transmitted in repetition of fixed-length time-slots called a TDMA cycle. Given a PR network, the goal of GNN is to find a TDMA cycle with the minimum delay time for each node to broadcast packets. GNN for the N-node-M-slot TDMA cycle problem consists of a neural network with N M binary neurons and a gradual expansion scheme. The neural network not only satisfies the constraints but also maximizes transmissions by two energy functions, whereas the gradual expansion scheme minimizes the cycle length by gradually expanding the size of the neural network. The performance is evaluated through extensive simulations in benchmark instances and in geometric graph instances with up to 1000 vertices, where GNN always finds better TDMA cycles than existing algorithms. The result in this paper supports the credibility of our GNN algorithm for a class of combinatorial optimization problems.

A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.

To reduce the damage of key exposures, forward-secure group signature schemes have been first proposed by Song. In the forward-secure schemes, a secret key of a group member is updated by a one-way function every interval and the previous secret key is erased. Thus, even if a secret key is exposed, the signatures produced by the secret keys of previous intervals remain secure. Since the previous forward-secure group signature schemes are based on the strong RSA assumption, the signatures are longer than pairing-based group signatures. In addition, the complexity of the key update or signing/verification is O(T), where T is the total number of intervals. In this paper, a forward-secure group signature scheme from pairings is proposed. The complexity of our key update and signing/verification is O(log T).