Public communication systems often crash in large scale disasters, critically hindering coordination among disaster responders. Survival rates can be greatly increased by breaking communication bottlenecks. We proposed a contingency cellular network (CCN) that aims to provide communication service to large amount of voluntary workers and victims in the early hours. CCN connects crashed base stations using wireless links to construct a multihop cellular network. Since, topology design problem is one of the important issues of CCN design. This research proposes two algorithms to solve the network topology design problem of CCN which is constructed by multiple operators' base stations. The degree of emergency and population of each stricken area are taken as the priority measure as well as the available resources as the constraint to determine the network topology. The network topology design problem is formulated as a K-Maximum Spanning Tree Problem with degree bound and had been proven NP Hard. A binary integer linear programming (BILP) algorithm is proposed to solve the optimal solution. Since the network topology is needed in urgent, a heuristic algorithm is also proposed to solve this problem quickly.

When a catastrophic natural disaster occurs, the efficiency of disaster response operation is crucial to life saving. However, communication systems, such as cellular networks, were usually crashed due to various causes that made coordination difficult for many disorganized disaster response workers extremely. Unfortunately, rapid deployment of many existing emergency communication systems relies on a good transportation system, which is usually not available in a catastrophic natural disaster. We propose an emergency communication system, Contingency Cellular Network (CCN), by connecting disconnected base stations together with wireless links and portable power generators. CCN can support existing mobile phone users with limited capability. Such a system can support a large number of voluntary workers in the early hours of a catastrophic natural disaster, thus saving many lives. Design philosophy and high level system architecture of our framework are presented in this paper.

DCCP is proposed to replace UDP for its ability of congestion control while maintaining its promptness by ignoring lost packets as UDP does. The network would suffer less congestion. However, whether the applications that switch from UDP to DCCP can maintain their needed performance or not is a big question. This paper investigates this problem by evaluating DCCP based VoIP vs. a variety of TCPs using NS-2 simulator. Our study shows that DCCP has a disadvantage in competing network bandwidth with existing TCPs. DCCP based VoIP may perform poorly in facing the competition of TCP traffics.

When stricken by a catastrophic natural disaster, emergency rescue operation is very critical to many lives. Many people trapped in the disastrous areas under collapsed buildings or landslides may have a large chance to survive if they are rescued in "Golden 72 Hours". Victims rescued from the debris and evacuated from their home jammed in shelters need life support material to support their lives. They also need to communicate to each other for various reasons. However, communication systems were usually down due to various reasons. The loss of communication systems and information networks made the rescue and relief operation extremely difficult. Many people died before they got a chance to be rescued. This paper analyzes the causes that paralyzed the entire communication systems in Jiji/Taiwan Earthquake and proposes a MANET based communication platform as well as a Rescue Information System for Earthquake Disasters that can support a large number of rescue volunteers under catastrophic natural disasters.

This paper proposes a MANET/VANET based group communication system, P2Pnet, to support the communication and information demand for mobile group users such as rescue teams in catastrophic disasters, army in battle fields, and mobile learning groups. We use the Jiji Earthquake as an example to illustrate the physical environment and to establish system requirements for a mobile group communication system that are suitable for the environments mentioned above. We have implemented the first phase prototype as well as two application experiments on top of P2Pnet: Rescue Information System for Earthquake Disasters (RISED) and a mobile English learning experiment conducted in the Nation Chengchi University.

In a MANET environment, communication links are unstable due to various reasons. Error rate is higher and bandwidth is smaller than fixed networks. Running conventional TCP protocol over MANET will suffer from severe performance degradation. To handle a packet loss, conventional TCP retransmits the lost packet from its source. However, when error rate is high, it may have to take several retransmissions to deliver a packet to its destination successfully. Considering that most applications on a MANET prefer shorter packet delivery time to higher bandwidth, this paper proposes a Hop-by-Hop TCP protocol for MANET aiming to accelerate packet delivery. Hop-by-Hop TCP makes every intermediate node in the transmission path execute a local TCP to guarantee the transmission of each packet on each link. The retransmission of a lost packet is right at the transmitting end of the link where the packet is lost. It takes less time in average to deliver a packet in a high error rate environment. The performance of our approach is evaluated by simulation using NS-2 simulator. Our experiments show that our proposed protocol outperforms TCP Reno by 25.7% in throughput and 25% reduction in average packet delivery time. The fairness requirement is also achieved while our proposed protocol coexists with other major TCP variants.

Some peer-to-peer (P2P) file sharing operation models over asymmetric networks have several shortcomings that may have a significant impact to the system and network performance: data transmission paths are highly redundant wasting a lot of backbone bandwidth; the download throughput in a peer node may be limited by the upward bandwidth of other peer nodes; TCP performance is deteriorated due to the blocking of acknowledge packets on the upward channel. These shortcomings severely impair the efficiency of P2P file sharing as well as network performance. We designed a UDP based transport mechanism at the application level to alleviate parts of problems caused by TCP

The paper presents a feasible and efficient methodology that improves client mobility management under an ubiquitous information service network. The authors base the system on the open integrated service network architecture and propose a hybrid infrastructure with facilities of both a centralized network management center (NMC) and a distributed home base node (HBN). They use LSDMk for choosing a HBN with minimum cost by computing the expected registration cost and location tracking cost according to users' future k-step movement and called frequencies. LSDM is a special case of LSDMk when k is equal to 0. In addition, they use a cache strategy to save location tracking cost. Running simulations, results show that the methodology is able to save up to 86% and 54% of the cost comparing to that of IS-41 in best and average cases, respectively, when the value of call-mobility ratio (CMR) is in the range of (1, 100), which means either clients are called with high frequencies or are moving with low mobilities. As the value of CMR goes down to the range of (0.01, 1), which means either clients are called with low frequencies or are moving with high mobilities, one may save up to 83%, 60%, and 10% costs in best, average, and worst cases, respectively.

In relational databases, a composition requires three operations: join, projection and duplicate elimination. An expensive external sort is required to eliminate duplicates in a large file. Most conventional composition algorithms take join and duplicate elimination as separate operations to reduce overhead on either operation, but not both. Direct composition algorithms outperform all these algorithms by executing the composition as a single primitive. We show that the direct composition can even outperform its component operation, join, under various conditions. Moreover, when the density of the joining attribute is high enough, the hot spot direct composition may even run faster as the operand relations become bigger. These results can encourage real DBMSs to remove duplicates in some relational operations, and thus, to preserve the closure property of the relational data model.

Intelligent agents have been shown to be a good approach to addressing the issues of limited capacity and unreliable wireless links in mobile computing. However, before the approach can be commercially viable, a set of management capabilities that support the controls of intelligent agents in a mobile environment need to be in place. Since controls can only be applied after the target agent is located, an effective agent search algorithm is an indispensable part of the management functions. In this paper, we propose a new algorithm, the highest probability first algorithm, for locating the target agent. The approach makes use of the execution time information to reduce cost and network traffic. The execution time of the agent on a server is assumed to be binomial distributed and therefore is more realistic.

The objective of this paper is to present a feasible and efficient methodology that improves client mobility management under ubiquitous information service network. We base our system on the Open Integrated Service Network Architecture and propose a hybrid infrastructure with facilities of both a centralized Network Management Center (NMC) and a distributed Home Base Node (HEN). We also have criteria for choosing a HEN with minimum cost by computing the expected registration cost and location tracking cost according to users characteristics and called frequencies. Running a simulation, results show that our methodology is able to save up to 40% of the cost comparing to that of IS-41 when the value of Call-Mobility Ratio (CMR) is in the range of (1, 100), which means either clients are called with high frequencies or are moving with low mobilities. As the value of CMR goes down to the range of (0.01, 1), which means either clients are called with low-frequencies or are moving with high mobilities we may save up to 50% cost.

In a mobile computing environment that supports mobile agents, a client can send an agent to visit a sequence of servers in the network. To track the location of agents becomes a critical problem in managing a mobile agent service network. This paper studies the agent search problem based on an open architecture proposed by Lien (see Proc. of the First Workshop on Mobile Computing, Hsing-Chu, Taiwan, p.2-9, 1995) and is currently being implemented in the National Chengchi University.

A composition requires three operations: join, project, and duplicate elimination. A hot-spot composition algorithm is proposed in an attempt to achieve savings on both join and external sort operations. The proposed algorithm reduces the effort of performing the join operation by using a novel hot-spot technique. Several experiments have been conducted, and it is shown that the hot-spot composition algorithm outperforms other algorithms under almost every condition. The composition operation is implemented as a primitive operation in the algorithm.>

The commenters point out that conjectures in the above-named paper (ibid., vol.C-33, no.4, p.323-333) concerning the structure of a least-cost generalized hypercube can be proved.>

A distributed algorithm that uses a node-join-tree approach for the minimum-spanning-tree problem in a communication network is developed. The algorithm needs at most (2e+n(n-1)/4) messages in O(n/sup 2/) time on a general random graph. In the best case, it needs only 2e messages in O(log n) time. The parameters e and n are the number of edges and nodes, respectively. Although the worst-case performance is not better than that of tree-join-tree algorithms under some extreme cases, simulation results show that it provides better performance in most cases. The algorithm is initialized from a single node, so that there is no need to wake up all nodes at the beginning. It is less complicated than other algorithms, so that a reliable implementation is easier to achieve. The results can be used to improve the algorithms for many other problems in distributed computing, such as leader-election, node-counting, deadlock-resolution, and message-broadcasting. >

Various versions of the file allocation problem on homogeneous two-level local multiaccess networks are examined. The problems associated with file allocation are more simple on two-level networks than on general point-to-point networks because the communication cost for accessing a file is reduced to a three-value variable. File allocation with storage-limit constraints is still NP-hard. The optimal solution, given these conditions, involves transformation into a pure zero-one integer programming problem and a search algorithm based on E. Balas's additive algorithm (1965). In the case in which the system is dominated by the communication cost, the simple file allocation problem is polynomially solvable. An efficient heuristic algorithm with guaranteed performance is proposed for this special case.>

Concurrency control, distribution design, and query processing are some of the important issues in the design of distributed databases. In this paper, we have studied these issues with respect to a relational database on a local computer system connected by a multiaccess broadcast bus. A broadcast bus allows information to be distributed efficiently, and hence simplifies the solutions to some of these issues. A transaction model that integrates the control strategies in concurrency control and query processing is proposed. In concurrency control, the lock, unlock, and update of data are achieved by a few broadcasts. A dynamic strategy is used in query processing, as less data are transferred when compared to a static strategy. The status information needed in dynamic query processing can be conveniently obtained by broadcasting. Lastly, some NP-hard file placement problems are found to be solvable in polynomial time when updates are broadcast.

In this paper the distribution-design and query-processing problems for distributed databases on local multiaccess computer networks are studied. The broadcast capability of these networks allows information to be distributed efficiently. In the distribution-design problem, the distribution of independent files are studied. With the broadcasts of updates, the distribution of multiple copies of a single file can be solved optimally in polynomial time. However, the general problem with storage-capacity constraints is still NP-hard, and an efficient branch-and-bound method is proposed. In the query-processing problem, the semi-join concept is adopted. The propagation of reduction on dependent attributes is studied. Although the problem is NP-hard, less data transmission is needed with the broadcast of information.