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).

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

Previously, we have proposed an access point (AP) allocation algorithm in indoor environments for the Wireless Internet-access Mesh NETwork (WIMNET) using one gateway (GW) to the Internet. WIMNET consists of multiple APs that are connected wirelessly mainly by the Wireless Distribution System (WDS), to expand the coverage area inexpensively and flexibly. In this paper, we present two extensions of this algorithm to enhance the applicability to the large-scale WIMNET. One is the multiple GW extension of the algorithm to increase the communication bandwidth with multiple GWs, where all the rooms in the network field are first partitioned into a set of disjoint GW clusters and then, our previous allocation algorithm is applied to each GW cluster sequentially. The APs in a GW cluster share the same GW. The other is the dependability extension to assure the network function by maintaining the connectivity and the host coverage, even if one link/AP fault occurs, where redundant APs are added to the AP allocation by our previous algorithm. The effectiveness of our proposal in terms of the number of APs and the throughput is verified through simulations using the WIMNET simulator.

An approach of membership revocation in group signatures is verifier-local revocation (VLR for short). In this approach, only verifiers are involved in the revocation mechanism, while signers have no involvement. Thus, since signers have no load, this approach is suitable for mobile environments. Although Boneh and Shacham recently proposed a VLR group signature scheme from bilinear maps, this scheme does not satisfy the backward unlikability. The backward unlinkability means that even after a member is revoked, signatures produced by the member before the revocation remain anonymous. In this paper, we propose VLR group signature schemes with the backward unlinkability from bilinear maps.

This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in V such that any pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS_CLR, a construction stage first generates an initial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent search with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the best existing one. In particular, MIPS_CLR provides new lower bound solutions for several instances. The simulation results confirm the extensive search capability of our MIPS_CLR approach for the graph coloring problem.

A clique of a graph G(V,E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time energy-descent optimization algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that RaCLIQUE, the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.