There are two principal aspects of "mobility" in location-aware computing: (1) how to support mobility and (2) how to exploit it. This paper considers the latter, while many existing works only concentrate on the former. This work is trying to prove that the performance of location-aware systems will be greatly improved by understanding the user's movement. In this paper, we propose a novel location update protocol called state-based location update protocol (SLUP), which significantly minimizes the energy consumption of mobile client by exploiting a syntactic information of a user's movement. This concept is called mobility-awareness which is a kind of context-awareness. Moreover, there are three variations of the proposed protocol in terms of how to choose the optimal state: SLUP/BS, SLUP/UITR, and SLUP/IUT. Experimental results show that the proposed protocol outperforms the well-known existing protocols such as dead-reckoning and distance-based protocol, and that the SLUP/IUT approach can achieve different performance tradeoffs between energy efficiency and location accuracy by fine-tuning its algorithmic parameter Tiut.

Content-based image search has long been considered a difficult task. Making correct conjectures on the user intention (perception) based on the query images is a critical step in the content-based search. One key concept in this paper is how we find the user preferred low-level image characteristics from the multiple positive samples provided by the user. The second key concept is how we generate a set of consistent "pseudo images" when the user does not provide a sufficient number of samples. The notion of image feature stability is thus introduced. The third key concept is how we use negative images as pruning criterion. In realizing the preceding concepts, an image search scheme is developed using the weighted low-level image features. At the end, quantitative simulation results are used to show the effectiveness of these concepts.

In this paper, we present a novel forwarding scheme to enhance communication stability based on geographic routing in mobile ad hoc networks, which is called "Position-based Heuristic Forwarding" (PHF). For alternative solutions to traditional ad hoc routings, many geographic routing algorithms have been proposed. Most of the existing routings impose a certain restriction, planarity, on the graph structure of network for delivering messages to destination definitely. PHF achieves the guaranteed packet delivery over Unit Disk Graph, which is more widely employed graph model for the study of ad hoc networks. Accordingly, to eliminate the restriction of the routing algorithms enhances the probability to deliver messages successfully in networks with high nodes' mobility rate. In the simulation of PHF, we have evaluated the performance comparisons between PHF and its related work, Greedy Perimeter Stateless Routing (GPSR) and Dynamic Source Routing (DSR), which are the prominent geographic and conventional topology-based routing protocols, respectively. The results show that PHF provides higher packet delivery success rate indicating better communication stability and equal or less overhead than these work.

We discuss the problem of finding a dominant sequence for sending input data items from a low-end client to a server for computational intensive tasks under the realistic assumption of unpredictable communication behavior. Under this assumption, the client has to send the input data items using a specified sequence to maximize the number of computations performed by the server at any time. The sequence-finding problem is NP-hard for the general case. In this paper, we address three fundamental and useful applications: the product of two polynomials, matrices multiplication and Fast Fourier Transform. We show that the sequence-finding problems of the three applications can be solved optimally in linear time. However, we also show counter examples to rule out any possibility of finding a dominant sequence for sparse cases of the three applications. Finally, a simulation is conducted to show the usefulness of our method.

Research on low-power scan testing has been focused on the shift mode, with little consideration given to the capture mode power. However, high switching activity when capturing a test response can cause excessive IR-drop, resulting in significant yield loss due to faulty test results. This paper addresses this problem with a novel low-capture-power X-filling method by assigning 0's and 1's to unspecified bits (X-bits) in a test cube to reduce the switching activity in capture mode. This method can be easily incorporated into any test generation flow, where test cubes can be obtained during ATPG or by X-bit identification. Experimental results show the effectiveness of this method in reducing capture power dissipation without any impact on area, timing, and fault coverage.

A self-organizing wireless network has to deal with reliability and congestion problems when the network size increases. In order to alleviate such problems, we designed and analyzed protocols and algorithms for a reliable and efficient multiple-layer self-organizing wireless network architecture. Each layer uses a high-power root node to supervise the self-organizing functions, to capture and maintain the physical topology, and to serve as the root of the hierarchical routing topology of the layer. We consider the problem of adding a new root with its own rooted spanning tree to the network. Based on minimum-depth and minimum-load metrics, we present efficient algorithms that achieve optimum selection of root(s). We then exploit layer scheduling algorithms that adapt to network load fluctuations in order to optimize the performance. For optimality we consider a load balancing objective and a minimum delay objective respectively. The former attempts to optimize the overall network performance while the latter strives to optimize the per-message performance. Four algorithms are presented and simulations were used to evaluate and compare their performance. We show that the presented algorithms have superior performance in terms of data throughput and/or message delay, compared to a heuristic approach that does not account for network load fluctuations.

In this paper, we propose Split Multi-path Routing protocol with Load Balancing policy (SMR-LB) to improve TCP performance in mobile ad hoc networks. In SMR-LB, each intermediate node records how many primary paths are attempted to construct as well as which source nodes attempt to construct the primary path. Each intermediate node decides which primary path should be constructed by using the primary path and the source node ID information. As a result, SMR-LB can balance the loads and so reduce the probability of congestion and avoid the continuous link breakage time between the specific source and destination pair. Computer simulation results show that SMR-LB can improve TCP performance compared with the conventional protocols.

In this letter we consider topology control and routing problem in wireless networks where equipped with point-to-point wireless links such as directional antennas or free space optics. In point-to-point wireless networks, each node has a limited number of transceivers and hence can communicate with only a limited number of nodes within its transmission range. The selection of the limited number of neighbors is very critical for the network performance. In this letter, we propose a topology control algorithms which consider the topology control and routing of each demand is considered simultaneously. For this, we introduce the degree constraint shortest path problem for finding optimal (shortest) paths in wireless point-to-point networks. Also, we propose two topology control algorithms: minimum hop (MHA) and resource availability ratio (RAR) algorithm. The resource availability ratio algorithm considers not only the available link bandwidth but also the available interfaces between neighbors. By simulation experiments, we compare the performance of each algorithm.

In this paper, we propose a protocol for multicast communication called Multicast Datagram Transfer Protocol (MDTP) to provide multicast for video broadcasting service on the Internet. MDTP is a one-to-many multicast communication protocol, which is constructed based on IPv4 unicast protocol by utilizing IP Router Alert Option, and it uses unicast addressing and unicast routing protocol. A mechanism is presented to allow a router to remove identical video stream, to duplicate a video stream, and to forward each copy of the duplicated video stream to its destinations. Ordinary IP routers that do not support MDTP will treat the MDTP packets as normal unicast packets. Hence, gradual deployment is possible without tunneling technique. With a delegation mechanism, MDTP router is also able to handle request from clients, and serve the requested video stream. The simulation results show that the average bandwidth usage of MDTP is close to the average bandwidth usage of IP multicast. MDTP also has greater efficiency than XCAST, and its efficiency becomes significant for a large number of clients.

Since congestion is very likely to happen in the Internet, locating congested areas (path segments) along a congested path is vital to appropriate actions by Internet Service Providers to mitigate or prevent network performance degradation. We propose a practical method to locate congested segments by actively measuring one-way end-to-end packet losses on appropriate paths from multiple origins to multiple destinations, using a network tomographic approach. Then we conduct a long-term experiment measuring packet losses on multiple paths over the Japanese commercial Internet. The experimental results indicate that the proposed method is able to precisely locate congested segments. Some findings on congestion over the Japan Internet are also given based on the experiment.

This paper proposes χLIN6-NEMO, a network mobility protocol based on LIN6. LIN6 is a host mobility protocol in IPv6 and is based on separation of the location and the identifier. In IETF, NEMO Basic Support Protocol based on Mobile IPv6 is standardized as a network mobility protocol. NEMO Basic Support Protocol as well as Mobile IPv6, however, has several fundamental problems in its communication procedures such as inefficient routing, header overhead due to tunneling, and single point of failure. χLIN6-NEMO makes use of the address structure of LIN6 and solves these problems. A fixed node and a Mobile IPv6 node can be connected to a mobile network provided by χLIN6-NEMO. A mobile network provided by NEMO Basic Support Protocol can also be connected to a mobile network provided by χLIN6-NEMO. We implemented χLIN6-NEMO on NetBSD 1.6.2 Release. Our measurement results showed χLIN6-NEMO can provide network mobility with low overhead.

QMNF is a QoS-aware multicast routing protocol using N-hop dominating flooding and built upon a layered routing architecture. In this architecture, QMNF invites the N-hop flooding component and the shortest path routing table from OSPF by open signaling interfaces, floods the path-probing packets, and employs a two-pass resource reservation scheme to avoid unnecessary resource reservation. The QMNF is QoS-aware, loop-free, flexible and scalable, and improves network resource utilization. In our simulation, the performance of QMNF is compared with that of traditional flooding protocol with the shortest path resources reservation, a traditional flooding protocol with the widest path resources reservation, PIM and QMBF. The simulation results confirm that QMNF has a high success rate and good resource utilization, and it can distribute traffic in a network evenly.

When digital broadcasting services are provided through cable television (CATV) networks, viewers watching interactive programs such as quizzes or auctions may respond to the program within a short period. If these responses are transmitted in the upstream channel of the CATV networks using TCP/IP, they will result in burst traffic. The numerous TCP connections will trigger congestion in the upstream transmission facilities and will cause a significant delay in conventional Internet services such as web-browsing. The present paper proposes a new method of controlling the CATV upstream channel to avoid such congestion. We introduce class-based queues at each cable TV station, in which each service class is related to a type of interactive service. The status of the queue is relayed to the cable modems of subscribers using a CATV-specific MAC protocol. This queue-status information is used to suspend further initiation of TCP connections at cable modems. As a result, the TCP connections will be arbitrated in the CATV network, while the delay of the response transmission is traded for smoothing of the burst traffic. We numerically evaluate the effect of the proposed method using the time distribution of responses to an actual quiz program. The results show that the proposed method successfully suppresses interference of the burst traffic with conventional best-effort services.

The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.

Ants-based routing algorithms have attracted the attention of researchers because they are more robust, reliable, and scalable than other conventional routing algorithms. Since they do not involve extra message exchanges to maintain paths when network topology changes, they are suitable for mobile ad-hoc networks where nodes move dynamically and topology changes frequently. As the number of nodes increases, however, the number of ants (i.e., mobile agents or control messages) also increases, which means that existing algorithms have poor scalability. In this paper, we propose a scalable ant-based routing algorithm that keeps the overhead low while keeping paths short. Our algorithm uses a multistep TTL (Time To Live) scheme, an effective message migration scheme, and an efficient scheme for updating the probability of packet forwarding. Simulation experiments have confirmed that our proposed algorithm can establish shorter paths than the conventional ant-based algorithm with the same signaling overhead.

This paper presents an approach to specification-based testing of concurrent programs with representative test sequences generated from Statecharts. Representative test sequences are a subset of all possible interleavings of concurrent events that define the behaviors of a concurrent program. Because a program's correctness may be determined by checking whether a program implemented all behaviors in its specification or not, the program can be regarded as being correct if it can supply an alternative execution that has the same effects as the program's behavior with each representative test sequence. Based on this observation, we employ each representative test sequence as a seed to generate an automaton that accepts its equivalent sequences to reveal the same behavior. In order to effectively test a concurrent program, the automaton such generated accepts all sequences equivalent to the representative test sequence and it is used to control test execution. This paper describes an automated process of generating automata from a Statecharts specification and shows how the proposed approach works on Statecharts specifications through some examples.

IEEE 802.11 DCF is a contention-based channel access protocol, and medium access delay greatly increases as the number of contending stations in a service area increases. This severely affects on delay-sensitive video applications. In this paper, we focus on MAC-layer solutions for realizing high quality video transmission in 802.11 DCF networks. A new channel access protocol based on the timestamp (TS) of video packets is proposed for real-time video. The TS information is carried by RTP header from the video application to 802.11 MAC. For video packets with the same RTP TS, they are simultaneously transmitted in a single channel access. Additional contention and back-off processes can be avoided because the whole packets of a video frame are completely delivered. The proposed TS-based access protocol can be easily implemented by the DCF with packet bursting. In addition, it is backward compatible to the legacy DCF. Extensive simulations show that the TS-based channel access achieves lower cumulative distributions of application-level video frame delay when compared to the DCF protocol.

The homomorphic property of the public key cryptosystem has been exploited in order to achieve asymmetric fingerprinting such that only a buyer can obtain fingerprinted content. However, this requires many computations and a wide-band network channel because the entire uncompressed content must be encrypted based on the public key cryptosystem. In this paper, instead of the homomorphic property, we introduce the management of the enciphering keys for the symmetric cryptosystem. Based on a buyer's identity, a trusted center issues the buyer a partial sequence which is one of the two elements in the entire sequence. Although a merchant shares the entire sequence with the center, he cannot extract the buyer's key sequence from it. Such an information gap enables our protocol to be asymmetric and efficient. For each packet of content, the merchant produces two marked packets that contains a "0" or "1" information bit, and they are enciphered using the two elements from the entire sequence. Subsequently, the buyer obtains the two ciphertexts (the encrypted marked packets) containing the information bits of his identity. Since the merchant does not know the ciphertext decrypted by the buyer, an asymmetric property is achieved. In our protocol, before trade between a buyer and a merchant, the merchant can produce and compress the marked packets; this enables the reduction of both the computational costs for the encryption and the amount of data for transmission. Since only the enciphering operation is performed by a merchant in the on-line protocol, real-time operation may be possible.

The modeling of gate delays has always been one of the most difficult and market-sensitive works. In submicron designs, the second-order effects such as the input-to-output coupling capacitance have a significant influence on gate delay as shown in this paper. However, the accurate analysis of the input-to-output coupling capacitance effect has not been presented in previous research. In this paper, an analytical model for the influence of the input-to-output coupling capacitance on CMOS inverter delay is proposed, in which a novel algorithm for computing overshooting time is given. Experimental results show good agreement with Spice simulations.

The core technical issue in XML message brokers, which play a key role in exchanging information in ubiquitous environments, is processing a large set of continuous XPath queries over incoming XML streams. In this paper, a new system as an epochal solution for this issue is proposed. The system is designed to minimize the runtime workload of continuous query processing by transforming XPath expressions and XML streams into newly proposed data structures and matching them efficiently. Also, system performances are estimated both in terms of space and time, and verified through a variety of experimental studies, showing that the proposed system is practically linear-scalable and stable in terms of processing a set of XPath queries in a continuous and timely fashion.