In recent years, energy harvesting techniques have made it possible to overcome the energy resource limitation suffered by traditional Wireless Sensor Networks. In particular, it is now possible for the network to operate perpetually if sufficient energy is harvested to replenish the energy that is being consumed. Hence the need to prolong network lifetime is no longer the primary objective for the design of network routing protocols. Instead, the aim now is to maintain the network in a Energy Neutral state under which a certain performance level can be maintained perpetually. In this paper we propose a routing protocol, which we refer to as the Energy Neutral Routing (ENR) Protocol, that is able to achieve this objective. ENR also provides fair distribution of traffic loads and it is able to guarantee a linear bound on the total number of communication control messages exchanged, which in turn improves the overall distinct packet delivery ratio. Empirical studies are carried out to evaluate and compare the performance of ENR against other routing protocols.

Energy harvesting techniques have enabled the provisioning of alternative energy sources beside the conventional one which is typically provided by the batteries. Using such harvesting techniques together with proper energy management mechanisms, a Energy Neutral state can be achieved so that desired performance level can be supported perpetually. Existing energy neutral management mechanisms rely on the prediction of the amount of energy that can be harvested in the future. Such mechanisms suffer from the time consuming prediction processes and great fluctuations in the actual implementations. Hence, in this paper we propose real time adaptive energy management policies that enable energy neutral management based solely on observed information in the past instead of predicting the amount of energy that can be harvested in the future. We will show that these policies are throughput optimal in the sense that we are able to ensure that the data queue of each sensor node remain stable when the largest possible data rate is applied under different channel capacity scenarios. We also propose an energy harvest-store(use) method to reduce the energy losses caused by storing energy in non ideal energy buffers. Simulation studies show that our proposed throughput optimal policies and harvest-store(use) method are indeed able to improve the overall throughput as compared to existing schemes.

In existing studies of Message Ferry (MF) schemes in wireless ad hoc networks, routes for message ferries are often adopted from the solutions of the Traveling Salesman Problem (TSP) and its variants. In such existing solutions, a message ferry route is often assumed to be a simple cycle which has no repeated vertices nor edges. In this paper, we consider a more general case, where the route is a closed walk. In doing so, we generalize the Message Ferry Route (MFR) problem as the MFR* problem, and propose the An-Improved-Route (AIR) scheme to construct routes for the ferry. Simulation proves that the AIR scheme effectively reduces the delay of the MF schemes.

P2P-like applications are quickly gaining popularity in the Internet. Such applications are commonly modeled as graphs with nodes and edges. Usually nodes represent running processes that exchange information with each other through communication channels as represented by the edges. They often need to autonomously determine their suitable working mode or local status for the purpose of improving performance, reducing operation cost, or achieving system-level design goals. In order to achieve this objective, the concept of status configuration is introduced in this article and a mathematical correspondence is further established between status configuration and an optimization index ( OI ), which serves as a unified abstraction of any system design goals. Guided by this correspondence and inspired by the cross-entropy algorithm, a cross-entropy-driven self-organization mechanism (CESM) is proposed in this article. CESM exhibits the self-organization property since desirable status configurations that lead to high OI values will quickly emerge from purely localized interactions. Both theoretical and experimental analysis have been performed. The results strongly indicate that CESM is a simple yet effective technique which is potentially suitable for many P2P-like applications.

In this paper, we propose a new node allocation scheme that is based on a probabilistic approach to protect a mobile ad hoc network (MANET) from partitioning. This scheme adopts the normal distribution for node placement and we refer to it as the normally(N)-distributed node allocation scheme (N-NAS). The proposed scheme is able to achieve high connectivity and good degree of coverage by controlling the positions of nodes in the MANET in a fully distributed way. In this scheme, a theoretical upper bound of partition probability can be derived. In addition, unlike the existing schemes, N-NAS automatically initializes node positions when the MANET is just constructed. Extensive simulations are carried out to validate the performance of our proposed scheme.

Group mobility is prevalent in many MANET applications, such as disaster recovery, military actions, etc., and group partitions are unavoidable under such dynamic network. Group partitioning may result in frequent link disconnections, which hence affects the inter-group communication. In this paper, we introduce a framework for predicting potential group partitions in MANETs such that remedial actions can be taken in advance. The weighted linear prediction model is proposed in our work which is based on the linear displacement of a group instead of its instant velocity. The concept of safe distance is discussed and it is used in predicting the partition time of adjacent groups. The experiment shows that the prediction model displays its efficiency in prediction of group partitions.

Evolution programming (EP) is an important category of evolutionary algorithms. It relies primarily on mutation operators to search for solutions of function optimization problems (FOPs). Recently a series of new mutation operators have been proposed in order to improve the performance of EP. One prominent example is the fast EP (FEP) algorithm which employs a mutation operator based on the Cauchy distribution instead of the commonly used Gaussian distribution. In this paper, we seek to improve the performance of EP via exploring another important factor of EP, namely, the selection strategy. Three selection rules R1-R3 have been presented to encourage both fitness diversity and solution diversity. Meanwhile, two solution exchange rules R4 and R5 have been introduced to further exploit the preserved genetic diversity. Simple theoretical analysis suggests that through the proper use of R1-R5, EP is more likely to find high-fitness solutions quickly. Our claim has been examined on 25 benchmark functions. Empirical evidence shows that our solution selection and exchange rules can significantly enhance the performance of EP.

Globalization leads to an efficient new business paradigm generally known as Collaborative Virtual Enterprise (CVE) which demands flexible service orchestration and robust workflow execution. As two major service orchestration strategies, OWL-S and BPEL have their own strength and deficiencies. To meet the challenge in CVE, in this paper, we propose a Workflow Execution System (WES) that takes advantage of the complementary strengths of these two technologies. On the one hand, having semantic support, OWL-S is used in dynamic service discovery and composition at high level. On the other hand, at the concrete level, industry-based BPEL is exploited in service execution. The description of each Semantic Web service is enhanced with rule-based modeling of the essential business logic behind the service interface. In order to realize interoperability in OWL-S and BPEL without loss of semantic information, we further proposed an OWLS2BPEL Mapper to facilitate the workflow robustness and support rule evaluation to increase responsiveness to customers. A concrete scenario in PC manufacturing Collaborative Virtual Enterprise is analyzed to demonstrate the effectiveness of our workflow execution system.

Coverage is a fundamental problem in sensor networks. Sensor coverage, which reflects how well a sensor network is monitored by sensors, is an important measure for the quality of service (QoS) that a sensor network can provide. By noticing that mobility of sensors can be used to enhance the coverage of target field, some existing works have proposed several movement-assisted sensor deployment schemes. These works assume the target field to be a 2D space. In this paper, we study a generalized case of this problem whereby the target field can be a space range from 1D to 3D. We propose an unified framework which identifies four basic attributes for a good movement-assisted sensor deployment scheme. Based on these attributes, we present a unified scheme for the generalized case of the movement-assisted sensor deployment problem.

With an increasing complexity of business processes, self-healing capability is becoming an important issue in order to support robust service flow execution. In this paper, a dynamic self-healing mechanism is proposed, which can dynamically identify suitable alternatives and replace faulty services such that a service flow can be performed successfully despite of unexpected exceptions. This mechanism explicitly utilizes semantic Web services for service matching and selection of a composite service in business service flow, and Semantic Web services are equipped with rich business rules in a domain-dependent manner. We explore the self-healing mechanism for supporting self-healable service flow execution which is modeled in BPEL4WS. A demo system of self-healing capable service flow execution is built to validate its effectiveness by a concrete scenario, PC manufacturing application.

In recent years, inspired by the emerging Web services standard and peer-to-peer technology, a new federated service providing (FSP) system paradigm has attracted increasing research interests. Many existing systems have either explicitly or implicitly followed this paradigm. Instead of exchanging files, peers in FSP systems share their computation resources in order to offer domain-specific services. In this paper, we focused on the coordination problem of how to self-organize the service group structures in response to the varying service demand. We presented our solution in the form of a coordination mechanism, which includes a labor-market model, a recruiting protocol, and a policy-driven decision architecture. Peers make their service providing decisions based on their local policies, which can be added, removed, or modified by users. A general methodology is introduced in this paper to facilitate policy design. Specifically, a heuristic inspired by the extremal optimization technique is utilized to handle potential inconsistencies among policies. A stimulus-response mechanism was further applied to make the decision process adjustable. Experiments under five application scenarios verified our ideas and demonstrated the effectiveness of our coordination mechanism.

Peer-to-peer (P2P) networks establish loosely coupled application-level overlays on top of the Internet to facilitate efficient sharing of resources. They can be roughly classified as either structured or unstructured networks. Without stringent constraints over the network topology, unstructured P2P networks can be constructed very efficiently and are therefore considered suitable to the Internet environment. However, the random search strategies adopted by these networks usually perform poorly with a large network size. In this paper, we seek to enhance the search performance in unstructured P2P networks through exploiting users' common interest patterns captured within a probability-theoretic framework termed the user interest model (UIM). A search protocol and a routing table updating protocol are further proposed in order to expedite the search process through self organizing the P2P network into a small world. Both theoretical and experimental analyses are conducted and demonstrated the effectiveness and efficiency of our approach.

Coverage is a fundamental problem in sensor networks. In this paper, we addressed the coverage problem from two different view points and refer to them as the worst and best- case coverage problems. Existing work on these two problems assumed that the coverage degree is one (i.e. the target area falls within the sensing range of at least one sensor). In this paper, we address thek-coverage problem, where the coverage degree is a user-defined parameterk. This is a generalization of the earlier work where onlyk=1 is assumed. By combining geometric and algorithmic techniques, we establish an optimal algorithm to solve the two variants of the k-coverage problem in polynomial time.

In this paper, we investigate the problem of grouping the sensor nodes into clusters to enhance the overall scalability of the network. A selected set of nodes, known as gateway nodes, will act as cluster-heads for each cluster and the objective is to balance the load among these gateways. Load balanced clustering increases system stability and improves the communication between the various nodes in the network. We call the problem addressed in this paper as theload-balancedclusteringproblem(LBCP). We first show that a special case of LBCP (whereby the traffic load contributed by all sensor nodes are the same) is optimally solvable in polynomial time. We next prove that the general case of LBCP is NP-hard. We then proposed an efficient 2/3-approximation algorithm for the problem.

Wireless sensor networks have been receiving increasing attention in recent years due to their potential applications in the establishment of dynamic communications for emergency/rescue operations, disaster relief efforts, and military networks. In this paper, we investigate the problem of grouping the sensor nodes into clusters to enhance the overall scalability of the network. A selected set of nodes, known as gateway nodes, will act as cluster-heads for each cluster and the objective is to balance the load among these gateways. Load balanced clustering increases system stability and improves the communication between the various nodes in the network. We call the problem addressed in this paper as the load-balanced clustering problem (LBCP). We prove that LBCP is NP-hard and we proposed an efficient 3/2-approximation algorithm for the problem.

Abstract A collaborative virtual environment (CVE) allows geographically dispersed users to interact with each other and objects in a common virtual environment via network connections. One of the successful applications of CVE is multiplayer on‐line role‐playing game. To support massive interactions among virtual entities in a large‐scale CVE and maintain consistent status of the interaction among users with the constraint of limited network bandwidth, an efficient collaborative interaction management method is required. In this paper, we propose a behaviour‐based interaction management framework for supporting multiplayer role‐playing CVE applications. It incorporates a two‐tiered architecture which includes high‐level role behaviour‐based interaction management and low‐level message routing. In the high level, interaction management is achieved by enabling interactions based on collaborative behaviour definitions. In the low level, message routing controls interactions according to the run‐time status of the interactive entities. Collaborative Behaviour Description Language is designed as a scripting interface for application developers to define collaborative behaviours of interactive entities and simulation logics/game rules in a CVE. We demonstrate and evaluate the performance of the proposed framework through a prototype system and simulations. Copyright © 2006 John Wiley & Sons, Ltd.

In this paper, we address agent coordination from a dynamic systems perspective and propose a dynamic coordination model, which is inspired by biological metabolic systems. A new coordination mechanism through dynamic local adjustment (CDLA) is presented, and coordination is achieved when every agent utilizes explicitly the global system dynamics and performs iteratively a dynamic local adjustment procedure. The CDLA mechanism is investigated in an example multiagent shop floor system. The results show that the example manufacturing process is well-coordinated and the coordination approach is practically applicable and effective

We proposed a routing and resource reservation protocol that support both unicasting and multicasting for mobile ad hoc network (MANET). Unlike the wired network where the network topology is rather static, the topology of a MANET changes regularly depending on the mobility of the network nodes. Hence, integrating the resource reservation protocol into an on-demand routing protocol would be an efficient means to search for a path with the required bandwidth. Resources are temporarily reserved on the feasible paths during the path searching, and are committed only when the path is selected. Two reservation styles are supported which allow the sharing of resources by multiple data sources if needed.

Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belong to the same group. In this paper, we study the problem of finding feasible solutions for the delay constrained group multicast routing problem (DCGMRP). The routing problem in this case involves the construction of a set of delay bounded multicast trees with bandwidth requirements, one for each member of the group, for multicasting messages to other members of the group. We first show that the problem is NP-complete. Next, we propose a heuristic algorithm to find feasible solutions for this problem. Simulation results show that our proposed algorithm is able to achieve a high probability of finding feasible solutions for DCGMRP, whenever one exists.

To support real-time natural interaction in the Collaborative Virtual Environment (CVE) with limited network bandwidth and computer processing power, the development of an efficient interaction management mechanism is a key issue. In this paper, we propose a behavior based interaction management mechanism for managing the collaborative interactions among the distributed users in our developed SmartCU3D, an Internet CVE system. With this mechanism, message routing in the system becomes adaptive to the application and the users' runtime interaction. It is achieved by giving the Object-Oriented style collaborative behavior description along with the 3D environment definition for every individual CVE application. The motivation of this research is to develop a framework to support a flexible and adaptive interaction management mechanism for developing different CVE applications.

This paper addresses the problem of video server selection in a distributed video-on-demand system. The objective of the problem is to balance the load among video servers and to minimize the delay for the video requests to be served. In order to achieve this objective, a near optimal assignment algorithm is proposed for video server selection. Empirical study shows that our proposed algorithm is able to achieve good load balancing performance as compared to some landmark algorithms.

The personal communication network (PCN) is an emerging wireless network that promises many new services for the telecommunication industry. The proliferation of demands for extending wireless services to integrated services which supports the transmission of data and multimedia information has resulted in the need for broadband wireless systems that are able to provide service capabilities similar to those of wireline networks. The ATM cell-relay paradigm is one possible approach to provide broadband wireless transmission with PCNs using the ATM switching networks for interconnection of PCN cells. In an ATM-based PCN, the communication path between a pair of mobile terminals might be elongated due to the mobility of the terminals. The link allocation problem is that of allocating backbone links among ATM switches to reduce the effects of terminal mobility on the performance of ATM-based PCNs. Huang and Wang (1997) have shown that this problem is NP-complete. In this paper, we propose a new efficient heuristic algorithm for the link allocation problem. One novel feature of our algorithm is that we are able to derive sufficient conditions under which our algorithm is able to guarantee optimal solutions. Our empirical study shows that the average lengths of communication paths obtained by our algorithm are shorter than those obtained by Huang and Wang's algorithm. In addition, the number of successfully established paths obtained by our algorithm is significantly more than that obtained by the aforementioned.

This paper considers the problem of reconfiguring two-dimensional degradable VLSI/WSI arrays under the constraint of row and column rerouting. The goal of the reconfiguration problem is to derive a fault-free subarray T from the defective host array such that the dimensions of T are larger than some specified minimum. This problem has been shown to be NP-complete under various switching and routing constraints. However, we show that a special case of the reconfiguration problem is optimally solvable in linear time. Using this result, a new fast and efficient reconfiguration algorithm is proposed. Empirical study shows that the new algorithm indeed produces good results in terms of the percentages of harvest and degradation of VLSI/WSI arrays.

The link allocation problem is that of allocating backbone links among ATM switches to reduce the effects of terminal mobility on the performance of ATM-based personal communication networks (PCN). Huang and Wang (1997) have shown that this problem is NP-complete. In this paper, we propose a new efficient heuristic algorithm for the link allocation problem. One novel feature of our algorithm is that we are able to derive sufficient conditions under which our algorithm is able to guarantee optimal solutions. Our empirical study shows that the average lengths of communication paths obtained by our algorithm are shorter than those obtained by Huang and Wang's algorithm. In addition, the number of successfully established paths obtained by our algorithm is significantly greater than that obtained by the latter.

This paper consider the problem of reconfiguring two dimensional very large scale integration (VLSI/WSI) arrays via the degradation approach. In this approach, all elements are treated uniformly and no elements are dedicated as spares. The goal is to derive a fault-free subarray T from the defective host array such that the dimensions of T are larger than some specified minimum. This problem has been shown to be NP-complete under various switching and routing constraints. However, we show that a special case of the reconfiguration problem with row bypass and column rerouting capabilities is optimally solvable in linear time. Using this result, a new fast and efficient reconfiguration algorithm is proposed. Empirical study shows that the new algorithm indeed produces good results in terms of the percentages of harvest and degradation of VLSI/WSI arrays.

In this paper, we present a new class of linear time heuristic algorithms for reconfiguring RRAMs. One novel feature of our algorithms is that we are able to derive new bounds on the fault counts for fast detection of reparable and irreparable RRAMs. Another novel feature is that, based on our algorithms, we are able to identify a new polynomial time solvable instance of the reconfiguration problem. Empirical results indicate that our new class of algorithms is indeed fast and effective.

The problem of reconfiguring memory arrays using spare rows and spare columns is known to be NP-complete and has received a great deal of attention in recent years. For reason of cost effectiveness, it is desirable in practice to find minimum reconfiguration solutions. While numerous algorithms have been proposed to find minimum reconfiguration solutions, they all run in worst case exponential time complexities. On the other hand, existing heuristic algorithms with fast polynomial running time cannot guarantee minimum solutions. This paper presents a provably good heuristic algorithm for finding minimum reconfiguration solution. Using random bipartite graphs, we prove that the reconfiguration problem is almost always optimally solvable with our new algorithm in polynomial time for all practical purposes. We also show that our algorithm can be used to estimate the number of spare rows and columns that are required to achieve a given percentage of yield for RRAM's with known defect probabilities.