Search

Various issues on network routing in a mobile ad-hoc network (MANET) have been studied with outstanding results. However, there is still room for improvement with regard to data accessibility, especially when the number of nodes increases in the network. To enhance the data accessibility in a MANET, a few replica allocation schemes have been proposed. In these schemes, the nodes are partitioned into groups so that each group has as many different data items as possible. However, grouping in a MANET requires an enormous amount of communication cost, since the network topology is changed dynamically. In this paper, we propose a scalable replica allocation scheme in which the nodes are grouped based on the mobility of the nodes. Grouping in the proposed scheme is done with one-hop communications in a fully distributed manner. Within each group, replicas are allocated to the group nodes based on the estimated data access frequencies that are computed periodically by the allocator of the group. It turns out that grouping with mobility and utilizing the estimated access frequency information enhances the stability of the topology of each group as well as the data accessibility. We evaluate the proposed scheme by simulations with the Network Simulator NS-3 along with the analytical evaluations. The results of simulations and analytical evaluations demonstrate the effectiveness of the proposed scheme in terms of communication cost. The proposed scheme reduces the communication cost by 347.1 % on average over the existing replica allocation scheme, while achieving comparable data accessibility.

We study a forwarding strategy in opportunistic networks which are one of the most challenging networks among mobile ad-hoc networks. In opportunistic networks, a node does not have knowledge about the entire network topology, which is essential in the mobile ad-hoc network's forwarding strategy. Thus, node behavior is exploited to calculate future contact opportunities for forwarding a message. Utilizing social network analysis (e.g., similarity and centrality) has been proposed to improve the accuracy of the calculation task. This paper proposes a forwarding strategy based on an analysis of network topology. In the proposed strategy, each node takes a sequence of snapshots of its first-order neighbors during a warm-up period. Each node exchanges its own snapshots with each other, and then aggregates the snapshots in order to extract the network topology information. The extracted network topology is analyzed by social network analysis methods: compactness and algebraic connectivity. Forwarding decisions are made using the analysis of the features (compactness and algebraic connectivity). We present simulations using NS-2 and the home-cell community-based mobility model to show that the proposed forwarding strategy results in delay performances similar to the epidemic forwarding scheme, while maintaining reasonable network traffic. In addition, we demonstrate that the proposed strategy outperforms the SimBet and PRoPHET forwarding schemes with various communication ranges and memory space.

This paper proposes a new group-based acceleration data structure called gkDtree for interactive ray tracing of dynamic scenes. The main idea of the gkDtree is to construct the acceleration structure with a multi-level hierarchy, and to integrate a parallelization approach to result in a faster update and a more efficient tree traversal. A gkDtree can be viewed as a set of kd-trees, each of which is a local acceleration structure corresponding to a group. For a gkDtree, a scene is divided into several groups based on a scene graph. The local acceleration structure of each group involving only dynamic primitives is rebuilt. To achieve higher parallelization, dependencies among groups in different levels are removed before rebuilding occurs in parallel. To enhance the scalability of parallelization, a simple and fast load-balancing scheme is introduced. Furthermore, we apply a variety of accurate SAH (surface area heuristic) algorithms into tree generation for both static and dynamic groups. The experimental results show that a gkDtree has a real-time update performance. It has an update performance that is up to 166 times faster than a kd-tree for our test scenes in a six-core hardware system environment. Furthermore, the results also show that tree traversal performance of a gkDtree is competitive with that of a kd-tree.

In this paper we propose an automated negotiation system that can efficiently carry out multilateral negotiations with multi-attributes in pervasive computing environments. For the multilateral negotiation system proposed in our study, an e-commerce framework for pervasive computing environments in which the components can dynamically join and disjoin a virtual market is also introduced. This framework overcomes the locality of pure ad hoc networks and supports efficiently multilateral negotiation models in pervasive computing environments. In order to achieve the applicability toward multilateral negotiations, the concept of a mediator agent and the bilateral negotiation scheme based on linear programming is utilized for the proposed system. The experimental results show that the proposed system produces higher joint profits in negotiations about 5% and is about 96 times faster in reaching agreements on the average under the condition of agreement for reciprocity than a negotiation system based on the trade-off mechanism.

As a 3D scene becomes increasingly complex and the screen resolution increases, the design of an effective memory architecture is one of the most important issues for 3D rendering processors. We propose a pixel rasterization architecture that performs the depth test twice, before and after texture mapping. The proposed architecture eliminates memory bandwidth waste due to fetching unnecessary obscured texture data by performing the depth test before texture mapping. It also reduces the miss penalties of the pixel cache by using a prefetch scheme-that is, a frame memory access, due to a cache miss at the first depth test, is done simultaneously with texture mapping. We have built a trace-driven simulator for the proposed architecture. To validate the proposed architecture, the results of various simulations are provided. The proposed pixel rasterization architecture achieves memory bandwidth effectiveness and reduces power consumption while producing high-performance gains.

This paper proposes an out-of-order execution control scheme that can be effectively applied to a coprocessor for embedded systems. A floating-point coprocessor has generally multiple pipelines such as a floating-point adder, a floating-point multiplier, a floating-point divider and a load/store pipelines. In order to utilize fully these pipelines, a constraint-based dynamic control scheme is designed for a coprocessor. This control scheme can be achieved by a data dependency checking, a resource conflict checking, and an exception prediction technique. With this control scheme a coprocessor can execute its instructions out of order without an extra hardware unit for out-of-order execution control.

An approach for designing a hybrid parallel system that can perform different levels of parallelism adaptively is presented. An adaptive parallel computer vision system (APVIS) is proposed to attain this goal. The APVIS is constructed by integrating two different types of parallel architectures, i.e. a multiprocessor based system (MBS) and a memory based processor array (MPA), tightly into a single machine. One important feature in the APVIS is that the programming interface to execute data parallel code onto the MPA is the same as the usual subroutine calling mechanism. Thus the existence of the MPA is transparent to the programmers. This research is to design an underlying base architecture that can be optimally executed for a broad range of vision tasks. A performance model is provided to show the effectiveness of the APVIS. It turns out that the proposed APVIS can provide significant performance improvement and cost effectiveness for highly parallel applications having a mixed set of parallelisms. Also an example application composed of a series of vision algorithms, from low-level and medium-level processing steps, is mapped onto the MPA. Consequently, the APVIS with a few or tens of MPA modules can perform the chosen example application in real time when multiple images are incoming successively with a few seconds inter-arrival time.

Many suboptimal motion vector search algorithms have been proposed because the full search algorithm, which is an optimal method, requires huge computational cost. Most of these algorithms find motion vectors simply from the center of the search window. In this paper, we propose an efficient motion vector search algorithm which, in order to predict the initial search point, exploits the global motion information obtained from the previous three frames and the local motion information regarding the motion vectors of the neighboring blocks of the current block. Our proposed algorithm searches for a motion vector from this initial search point, instead of from the center of the search window, using either the diamond search algorithm [J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, ‘‘A novel unrestricted center-biased diamond search algorithm for block motion estimation,’’ IEEE Trans. Circuits Syst. Video Technol. 8(4), 369–377 (1998) and S. Zhu and K. Ma, ‘‘A new diamond search algorithm for fast block matching motion estimation,’’ in ICICS’97, pp. 9–12, Singapore (Sept. 1997)] or the unrestricted small diamond search algorithm which performs its search always with a smaller diamond search pattern. Experimental results show that our proposed algorithm is faster than other suboptimal block matching algorithms while it maintains lower average block distortion.