Search

Presents an incremental design of scalable interconnection networks in multicomputer systems using basic building blocks. Consideration of both network topologies and routing algorithms; Use of worm-hole-routed small-scale two-dimensional meshes as basic building blocks; Minimum requirement to expand networks; Adoption of original algorithms designed from turn model.

It is desirable for the load in a distributed system to be balanced evenly. A dynamic process migration protocol is needed in order to achieve load balancing in a user transparent manner. A distributed algorithm for load balancing which is network topology independent is proposed in this paper. Different network topologies and low-level communications protocols affect the choice of only some system design parameters. The "drafting" algorithm attempts to compromise two contradictory goals: maximize the processor utilization and minimize the communication overhead. The main objective of this paper is to describe the dynamic process migration protocol based on the proposed drafting algorithm. A sample distributed system is used to further illustrate the drafting algorithm and to show how to define system design parameters. The system performance is measured by simulation experiments based on the sample system. [ABSTRACT FROM AUTHOR]

Presents a correction to the article "Optimal Load Balancing in a Multiple Processor System with Many Job Classes," by Lionel M. Ni and Kai Hwang in the May 1985 issue, with regards to the Load Balancing Algorithm.

Crowdedness spot is a crowded area with an abnormal number of objects. Detecting the crowdedness spots of moving vehicles in an urban area is essential to many applications. An intuitive method is to cluster the objects in areas to get the density information. Unfortunately, the data capturing vehicle mobility possesses some new features, such as highly mobile environments, supremely limited size of sample objects, and nonuniform biased samples, and all these features have raised new challenges that make traditional density-based clustering algorithms fail to retrieve the real clustering property of objects, making the results less meaningful. In this paper, we propose a novel nondensity-based approach called mobility-based clustering. The key idea is that sample objects are employed as “sensors” to perceive the vehicle crowdedness in nearby areas using their instant mobility rather than the “object representatives.” As such, the mobility of samples is naturally incorporated. Several key factors beyond the vehicle crowdedness have been identified, and techniques to compensate these effects are accordingly proposed. Furthermore, taking the detected crowdedness spots as a label of the taxi, we can identify one particular taxi to be a crowdedness taxi that crosses a number of different crowdedness spots. We evaluate the performance of our methods and baseline approaches based on real traffic situations (to retrieve the real traffic crowdedness) and real-life data sets. Finally, the interesting findings are provided for further discussions. [ABSTRACT FROM PUBLISHER]

A sustainable market-like computational grid has two characteristics: it must allow resource providers and resource consumers to make autonomous scheduling decisions, and both parties of providers and consumers must have sufficient incentives to stay and play in the market. In this paper, we formulate this intuition of optimizing incentives for both parties as a dual-objective scheduling problem. The two objectives identified are to maximize the success rate of job execution and to minimize fairness deviation among resources. The challenge is to develop a grid scheduling scheme that enables individual participants to make autonomous decisions while producing a desirable emergent property in the grid system; that is, the two systemwide objectives are achieved simultaneously. We present an incentive-based scheduling scheme, which utilizes a peer-to-peer decentralized scheduling framework, a set of local heuristic algorithms, and three market instruments of job announcement, price, and competition degree. The performance of this scheme is evaluated via extensive simulation using synthetic and real workloads. The results show that our approach outperforms other scheduling schemes in optimizing incentives for both consumers and providers, leading to highly successful job execution and fair profit allocation. [ABSTRACT FROM AUTHOR]

In unstructured peer-to-peer (P2P) systems, the mechanism of a peer randomly joining and leaving a P2P network causes a topology mismatch between the P2P logical overlay network and the physical underlying network, incurring a large volume of redundant traffic in the Internet. In order to alleviate the topology mismatch problem, we propose Adaptive Connection Establishment (ACE), an algorithm for building an overlay multicast tree among each source node and the peers within a certain diameter from the source peer and further optimizing the neighbor connections that are not on the tree while retaining the search scope. Our simulation study shows that this approach can effectively solve the mismatch problem and significantly reduce P2P traffic. We further study the trade-offs between the topology optimization rate and the information exchange overhead by changing the diameter used to build the tree. [ABSTRACT FROM AUTHOR]

Abstract Animation is a commonly used technique in information visualization for smooth transitions between different views. When observing animations of moving objects, people often need to track several specific objects while identify the major trend of movement simultaneously. In this paper, we propose a novel focus+context grouping technique to facilitate target tracking and trend identification. It divides objects into several groups based on a comprehensive tree cut algorithm and generates a staggering animation in which groups are animated sequentially. A balance between efficiency and accuracy is achieved for an effective animation planning. To evaluate the effectiveness of the proposed technique, a carefully designed user study is conducted. The results indicate that focus+context grouping is effective for users to track targets without losing context (i.e., major trend of movement). Based on the study, we discuss advantages and limitations of the proposed grouping technique and conclude with design implications. [ABSTRACT FROM AUTHOR]

Deploying wireless sensor networks in the ocean poses many challenges due to the harsh conditions of the ocean and the nonnegligible node mobility. In this paper, we propose hybrid ocean sensor networks called drifting restricted floating ocean sensor networks (DR-OSNs) for long-term maritime surveillance monitoring tasks, which combines both the advantages of wireless sensor networks and underwater wireless acoustic sensor networks. We present a localization scheme termed localization for double-head maritime sensor networks (LDSN) for DR-OSNs, which leverages the unique characteristics of DR-OSNs to establish the whole localization system after the network is deployed from a plane or a ship, and it does not need the presence of designated anchor nodes deployed underwater. The whole localization process consists of three steps with algorithms self-moored node localization (SML), underwater sensor localization (USD), and floating-node localization algorithm (FLA). The first step is for the super group nodes to localize their underwater moored nodes via an SML algorithm by leveraging the free-drifting movement of their surface nodes. Once the moored nodes in the super group nodes have localized themselves, they turn into anchor nodes underwater. Thus, in the second step, with the help of these new anchor nodes, the unlocalized underwater moored nodes use the USD algorithm to localize their positions. In the last step, when the free-drifting floating nodes without a Global Positioning System (GPS) module need to know their instant position, they apply the FLA to figure out their position. We conduct extensive simulations to evaluate the scheme, with the results indicating that LDSN achieves high localization accuracy and is an effective localization scheme for DR-OSNs. [ABSTRACT FROM PUBLISHER]

Sensor networks have emerged as a promising technology with various applications, where power efficiency is one of the critical requirements. The recent IEEE 802.15.4 standard offers a promising platform for wireless sensor networks. Since each node can act as a coordinator or a device in the IEEE 802.15.4 standard, 802.15.4-based sensor networks have various possible network topologies. To reduce power consumption, in this paper, we try to construct network topologies with a small number of coordinators while still maintaining network connectivity. By reducing the number of coordinators, the average duty cycle is reduced and the battery life is prolonged. Three topology control algorithms are proposed in this paper. Self-pruning (SP) is the simplest one with O(1) running time and provides the shortest path to the sink node. Ordinal pruning (OP) can significantly improve SP in terms of power saving with O(n) running time. Layered pruning (LP) is a trade off between the first two pruning algorithms with O(√n) running time and has a slightly higher power consumption than OP. Furthermore, all three algorithms are independent of the physical radio propagation characteristics. Extensive simulations have been performed to verify the effectiveness of the proposed topology control schemes. [ABSTRACT FROM AUTHOR]

RFID tag identification is a crucial problem in UHF RFID systems. Traditional tag identification algorithms can be classified into two categories, ALOHA-based and tree-based. Both of them are inefficient due to the incidental high coordination cost. In this paper, we bring CSMA into UHF RFID systems to enhance tag read rate by reducing coordination cost. However, it is not straightforward due to the simple hardware design of passive RFID tags, which is unable to sense the transmissions or collisions of other tags. To tackle this challenge, we propose receiver-based CSMA (RCSMA) in this paper. In RCSMA, the reader notifies the tags channel condition. According to different sensing results of reader's notifications, the tags take corresponding actions, e.g., random back off. RCSMA does not require special RFID tag hardware design. An absorbing Markov chain model is presented to analyze the performance of RCSMA and shown to be consistent with the simulation results. Compared with optimized ALOHA-based algorithms and optimized tree-based algorithms, RCSMA can enhance the tag read rate by 30-70 percent under different reader and tag data rates. [ABSTRACT FROM AUTHOR]

Intercontact time between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs) and central to forwarding algorithms and the end-to-end delay. Due to prohibitive costs, little work has conducted experimental study on intercontact time in urban vehicular environments. In this paper, we carry out an extensive experiment involving thousands of operational taxies in Shanghai city. Studying the taxi trace data on the frequency and duration of transfer opportunities between taxies, we observe that the tail distribution of the intercontact time, that is, the time gap separating two contacts of the same pair of taxies, exhibits an exponential decay, over a large range of timescale. This observation is in sharp contrast to recent empirical data studies based on human mobility, in which the distribution of the intercontact time obeys a power law. By analyzing a simplified mobility model that captures the effect of hot areas in the city, we rigorously prove that common traffic influxes, where large volume of traffic converges, play a major role in generating the exponential tail of the intercontact time. Our results thus provide fundamental guidelines on design of new vehicular mobility models in urban scenarios, new data forwarding protocols and their performance analysis. [ABSTRACT FROM AUTHOR]