We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $rac{15}{16}n^2+O(n)$ swaps for k=3.

We present a power-saving method for large-scale storage systems of cloud data sharing services, particularly those providing media (video and photograph) sharing services. The idea behind our method is to periodically rearrange stored data in a disk array, so that the workload is skewed toward a small subset of disks, while other disks can be sent to standby mode. This idea is borrowed from the Popular Data Concentration (PDC) technique, but to avoid an increase in response time caused by the accesses to disks in standby mode, we introduce a function that predicts future access frequencies of the uploaded files. This function uses the correlation of potential future accesses with the combination of elapsed time after upload and the total number of accesses in the past. We obtain this function in statistical analysis of the real access patterns of 50,000 randomly selected publicly available photographs on Flickr over 7,000 hours (around 10 months). Moreover, to adapt to a constant massive influx of data, we propose a mechanism that effectively packs the continuously uploaded data into the disk array in a storage system based on the PDC. To evaluate the effectiveness of our method, we measured the performance in simulations and a prototype implementation. We observed that our method consumed 12.2% less energy than the static configuration (in which all disks are in active mode). At the same time, our method maintained a preferred response time, with 0.23% of the total accesses involving disks in standby mode.

With aggressive device scaling, timing failures have become more prevalent due to manufacturing defects and process variations. When timing failure occurs, it is important to take corrective actions immediately. Therefore, an efficient and fast diagnosis method is essential. In this paper, we propose a new diagnostic method using timing information. Our method approximately estimates all the segment delays of measured paths in a design, using inequality-constrained least squares methods. Then, the proposed method ranks the possible locations of delay defects based on the difference between estimated segment delays and the expected values of segment delays. The method works well for multiple delay defects as well as single delay defects. Experiment results show that our method yields good diagnostic resolution. With the proposed method, the average first hit rank (FHR), was within 7 for single delay defect and within 8 for multiple delay defects.

In this paper, we first propose ten new discrimination features of SAR images in the moving and stationary target acquisition and recognition (MSTAR) database. The Ada_MCBoost algorithm is then proposed to classify multiclass SAR targets. In the new algorithm, we introduce a novel large-margin loss function to design a multiclass classifier directly instead of decomposing the multiclass problem into a set of binary ones through the error-correcting output codes (ECOC) method. Finally, experiments show that the new features are helpful for SAR targets discrimination; the new algorithm had better recognition performance than three other contrast methods.

An integral attack is one of the most powerful attacks against block ciphers. We propose a new technique for the integral attack called the Fast Fourier Transform (FFT) key recovery. When N chosen plaintexts are required for the integral characteristic and the guessed key is k bits, a straightforward key recovery requires the time complexity of O(N2k). However, the FFT key recovery only requires the time complexity of O(N+k2k). As a previous result using FFT, at ICISC 2007, Collard etal proposed that FFT can reduce the time complexity of a linear attack. We show that FFT can also reduce the complexity of the integral attack. Moreover, the estimation of the complexity is very simple. We first show the complexity of the FFT key recovery against three structures, the Even-Mansour scheme, a key-alternating cipher, and the Feistel structure. As examples of these structures, we show integral attacks against Prøst, AES, PRESENT, and CLEFIA. As a result, an 8-round Prøst P128,K can be attacked with about an approximate time complexity of 279.6. For the key-alternating cipher, a 6-round AES and a 10-round PRESENT can be attacked with approximate time complexities of 251.7 and 297.4, respectively. For the Feistel structure, a 12-round CLEFIA can be attacked with approximate time complexities of 287.5.

A mobile ad hoc network (MANET) consists of mobile wireless terminals without using base stations. MANETs are expected to be utilized for various purposes such as traffic jam information announcements for vehicles and safety confirmation systems in disaster. Each MANET uses unique routing protocols that have been adapted for particular applications. Therefore, utilizing a common routing protocol for multiple MANETs is difficult. In this paper, we propose an Autonomous Clustering-based Inter-Domain Routing protocol to communicate between MANETs. Using the autonomous clustering, the proposed inter-domain routing scheme can change the network gateways between MANETs adaptively according to the network topology changes.

Network Coding-based Epidemic Routing (NCER) facilitates the reduction of data delivery delay in Delay Tolerant Networks (DTNs). The intrinsic reason lies in that the network coding paradigm avoids competitions for transmission opportunities between segmented packets of a large data file. In this paper, we focus on the impact of transmission competitions on the delay performance of NCER when multiple data files exist. We prove analytically that when competition occurs, transmitting the least propagated data file is optimal in the sense of minimizing the average data delivery delay. Based on such understanding, we propose a family of competition avoidance policies, namely the Least Propagated First (LPF) policies, which includes a centralized, a distributed, and a modified variants. Numerical results show that LPF policies can achieve at least 20% delay performance gain at different data traffic rates, compared with the policy currently available.

Machine learning is used in various fields and demand for implementations is increasing. Within machine learning, a Random Forest is a multi-class classifier with high-performance classification, achieved using bagging and feature selection, and is capable of high-speed training and classification. However, as a type of ensemble learning, Random Forest determines classifications using the majority of multiple trees; so many decision trees must be built. Performance increases with the number of decision trees, requiring memory, and decreases if the number of decision trees is decreased. Because of this, the algorithm is not well suited to implementation on small-scale hardware as an embedded system. As such, we have proposed Boosted Random Forest, which introduces a boosting algorithm into the Random Forest learning method to produce high-performance decision trees that are smaller. When evaluated using databases from the UCI Machine learning Repository, Boosted Random Forest achieved performance as good or better than ordinary Random Forest, while able to reduce memory use by 47%. Thus, it is suitable for implementing Random Forests on embedded hardware with limited memory.

This paper proposes and analyses an improved direction finding (DF) method that uses a rotating interferometer. The minimum sampling frequency is deduced in order to eliminate the phase ambiguity associated with a long baseline, the influence of phase imbalance of receiver is quantitatively discussed and the Root Mean Square Error (RMSE) of both bearing angle and pitch angle are also demonstrated. The theoretical analysis of the rotating interferometer is verified by simulation results, which show that it achieves better RMSE performance than the conventional method.

Even though cloud users want to keep their data on clouds secure, it is not easy to protect the data because cloud administrators could be malicious and hypervisor could be compromised. To solve this problem, hardware-based memory isolation schemes have been proposed. However, the data in virtual storage are not protected by the memory isolation schemes, and thus, a guest OS should encrypt the data. In this paper, we address the problems of the previous schemes and propose a hardware-based storage isolation scheme. The proposed scheme enables to protect user data securely and to achieve performance improvement.

This paper presents an inter-satellite link (ISL) reassignment method to optimize the snapshot routing performance for polar-orbit LEO satellite networks. When the snapshot routing tables are switching simultaneously in all satellites, we propose to reassign the inter-plane ISLs with regularity to improve the quality of the next snapshot, such as snapshot duration, on-board transceiver utilization ratio and end to end delay. Evaluations indicate that our method can attain equal-length snapshots regardless of the latitude of the polar area border, and so is superior to the natural partition method. Meanwhile, compared with the equal partition method which is used in the Iridium system, our method can prolong 82.87% snapshot duration, increase 8.68% on-board transceiver utilization ratio and reduce 5.30% average end to end delay of the whole network. Therefore, we believe that the ISL reassignment method can be efficiently applied in all practical polar-orbit LEO satellite networks.

In this paper, we present a new electro-optic (EO) probing system based on heterodyne detection. The use of a recirculating frequency shifter allows to expand the bandwidth of the system far beyond what is attainable with a conventional heterodyne EO set-up. The performance for the frequencies up to 50GHz is analysed to forecast the viability of the system up to the THz range.

In this paper, we analyze the rollback traffic in polar-orbit satellite networks that use the snapshot routing algorithm. The concept of diamond rollback links and polar rollback links are presented for the first time, and the numbers of diamond and polar rollback links in polar-orbit satellite networks are concisely formulated. Simulations are performed based on the Iridium and Teledesic system in NS2, and the results finally confirm our analysis. With this work, we can not only simplify the rollback loops avoidance scheme, but also provide guidance for future satellite network routing optimization and topology design.

Throughput capacity is of great importance for the design and performance optimization of mobile ad hoc networks (MANETs). We study the exact per node throughput capacity of MANETs under a general 2HR-(g, x, f) routing scheme which combines erasure coding and packet replication techniques. Under this scheme, a source node first encodes a group of g packets into x (x ≥ g) distinct coded packets, and then replicates each of the coded packets to at most f relay nodes which help to forward them to the destination node. All original packets can be recovered once the destination node receives any g distinct coded packets of the group. To study the throughput capacity, we first construct two absorbing Markov chain models to depict the complicated packet delivery process under the routing scheme. Based on these Markov models, an analytical expression of the throughput capacity is derived. Extensive simulation and numerical results are provided to verify the accuracy of theoretical results on throughput capacity and to illustrate how system parameters will affect the throughput capacity in MANETs. Interestingly, we find that the replication of coded packets can improve the throughput capacity when the parameter x is relatively small.

A re-configurable wavelength de-multiplexer for wave-length-division-multiplexed (WDM) radio-over-fiber (RoF) systems, which is specially designed for delivering frequency-modulated continuous-wave (FM-CW) signals, is newly developed. The principle and characteristics of the developed de-multiplexer are described in detail. Then the de-multiplexing performances of 4-channel WDM 32-GHz-band, 8-channel WDM 48-GHz-band, and 5-channel WDM 96-GHz-band FM-CW RoF signals are evaluated with the de-multiplexer.

A regional protection system based on a wireless Ad-Hoc network has been in operation since 2008 in Shiojiri City, Japan. Wireless terminals transmit data packets to a server via transponders situated around the city. In this paper, a new routing algorithm that takes into account the level of congestion of the transponders is proposed. Using computer simulations, the proposed algorithm is shown to reduce the packet loss rate compared to the previous algorithm which is based on minimization of the number of hops to the server. Also, the proposed algorithm is shown be have almost the same packet loss rate as the best routing decisions obtained by an exhaustive search. Furthermore, the simulations used recreate the actual movement of terminals, so the results show what will happen in a realistic environment.

In the case of a disaster such as an earthquake or a tsunami, the city, town, and village administration usually issues an evacuation advisory and other information through the Outdoor Public Address Speakers for the disaster reduction broadcasting system covering its area of jurisdiction. However, in areas those have previous experience of a disaster, people frequently voice the lack of audibility of the disaster reduction broadcast. In this research, we conducted a questionnaire survey on the residents in the central area of Ishinomaki City, Miyagi Prefecture, who are the victims of the Great East Japan Earthquake Disaster, on the audible quality of outdoor public address (PA) speakers of the disaster reduction broadcasting system so as to understand the current state of such broadcasts and to propose ideal methods of sending and receiving information at the time of a future disaster.

A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n3) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.

The emerging three-dimensional (3D) technology is considered as a promising solution for achieving better performance and easier heterogeneous integration. However, the thermal issue becomes exacerbated primarily due to larger power density and longer heat dissipation paths. The thermal issue would also be critical once FPGAs step into the 3D arena. In this article, we first construct a fine-grained thermal resistive model for 3D FPGAs. We show that merely reducing the total power consumption and/or minimizing the power density in vertical direction is not enough for a thermal-aware 3D FPGA backend (placement and routing) flow. Then, we propose our thermal-aware backend flow named TherWare considering location-based heat balance. In the placement stage, TherWare not only considers power distribution of logic tiles in both lateral and vertical directions but also minimizes the interconnect power. In the routing stage, TherWare concentrates on overall power minimization and evenness of power distribution at the same time. Experimental results show that TherWare can significantly reduce the maximum temperature, the maximum temperature gradient, and the temperature deviation only at the cost of a minor increase in delay and runtime as compared with present arts.

This paper proposes an algorithm for exemplar-based image inpainting, which produces the same result as that of Criminisi's original scheme but at the cost of much smaller computation cost. The idea is to compute mean and standard deviation of every patch in the image, and use the values to decide whether to carry out pixel by pixel comparison or not when searching for the best matching patch. Due to the missing pixels in the target patch, the same pixels in the candidate patch should be omitted when computing the distance between patches. Thus, we first compute the range of mean and standard deviation of a candidate patch with missing pixels, using the average and standard deviation of the entire patch. Then we use the range to determine if the pixel comparison should be conducted. Measurements with well-known images in the inpainting literature show that the algorithm can save significant amount of computation cost, without risking degradation of image quality.