This paper proposes a novel access control scheme with collision detection that utilizes multiple-input multiple-output (MIMO) technology. Carrier sense multiple access with collision detection (CSMA/CD) is used in Ethernet wired local area networks (LANs) for media access control (MAC). CSMA/CD can immediately abort a transmission if any collision is detected and is thus able to change to a retransmission state. In Ethernet, CSMA/CD results in a transmission efficiency of approximately 90% because the protocol makes the transmission band available for useful communication by this retransmission function. Conversely, in conventional wireless LANs (WLANs), the packet collisions due to interfering signals and the retransmission due to collisions are significant issues. Because conventional WLANs cannot detect packet collisions during signal transmission, the success of a transmission can only be determined by whether an acknowledgment (ACK) frame has been received. Consequently, the transmission efficiency is low — approximately 60%. The objective of our study is to increase the transmission efficiency of WLANs to make it at least equal to that of Ethernet. Thus, we propose a novel access control scheme with collision detection that utilizes MIMO technology. When preamble signals are transmitted before transmitting data packets from an antenna, the proposed scheme can detect packet collisions during signal transmission at another antenna; then, the affected packets are retransmitted immediately. Two fundamental technologies are utilized to realize our proposed scheme. The first technology is the access control protocol in the MAC layer in the form of the MIMO frame sequence protocol, which is used to detect signal interference. The other technology is signal processing in the physical (PHY) layer that actualizes collision detection. This paper primarily deals with the proposed MAC layer scheme, which is evaluated by theoretical analyses and computer simulations. Evaluation by computer simulations indicate that the proposed scheme in a transmission efficiency of over 90%.

In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm for spheres based on slab partitioning technique and a plane sweep method. We derive a theoretical upper bound on the time complexity of the algorithm. Our bound tells that if both the dimension and the maximum ratio of radii of two spheres are bounded, then our algorithm runs in O(n log n + K) time with O(n + K) space, where K denotes the number of pairs of colliding spheres.

In this work we present an energy efficient leader election protocol for anonymous radio network populated with n mobile stations. Previously, Nakano and Olariu have presented a leader election protocol that terminates, with probability exceeding 1- (f ≥ 1), in log log n+o(log log n)+O(log f) time slots [14]. As the above protocol works under the assumption that every station has the ability to transmit and monitor the channel at the same time, it requires every station to be equipped with two transceivers. This assumption, however, is unrealistic for most mobile stations due to constraints in cost, size, and energy dissipation. Our main contribution is to show that it is possible to elect a leader in an anonymous radio network where each station is equipped with a single transceiver. Quite surprisingly, although every station has only one transceiver, our leader election protocol still runs, with probability exceeding 1- (f ≥ 1), in log log n+o(log log n)+O(log f) time slots. Moreover, our leader election protocol needs only expected O(n) total awake time slots, while Nakano and Olariu's protocol needs expected O(nlog log n) total awake time slots. Since every leader election protocol needs at least Ω(n) awake time slots, our leader election protocol is optimal in terms of the expected awake time slots.

High-speed collision detection is important to realize a highly-safe intelligent vehicle. In collision detection, high-computational power is required to perform matching operation between discrete points on surfaces of a vehicle and obstacles in real-world environment. To achieve the highest performance, a hierarchical matching scheme is proposed based on two representations: the coarse representation and the fine representation. A vehicle is represented as a set of rectangular solids in the fine representation (fine rectangular solids), and the coarse representation, which is also a set of rectangular solids, is produced by enlarging the fine representation. If collision occurs between an obstacle discrete point and a rectangular solid in the coarse representation (coarse rectangular solid), then it is sufficient to check the only fine rectangular solids contained in the coarse one. Consequently, checks for the other fine rectangular solids can be omitted. To perform the hierarchical matching operation in parallel, a hierarchically-content-addressable memory (HCAM) is proposed. Since there is no need to perform matching operation in parallel with fine rectangular solids contained in different coarse ones, the fine ones are mapped onto a matching unit. As a result, the number of matching units can be reduced without decreasing the performance. Under the condition of the same execution time, the area of the HCAM is reduced to 46.4% in comparison with that of the conventional CAM in which the hierarchical matching scheme is not used.