Abstract Designing an appropriate evacuation plan in the event of large scale disasters is extremely important. A considerable research effort has been invested in effective mathematical models and algorithms for the evacuation of densely populated areas. Dynamic networks and flows, and the closely related sink location and evacuation problems are research directions that are being actively pursued at the moment. In this work, we propose an extension of the sink location problem in dynamic networks that is suitable for planning the evacuation of remote and sparsely populated communities. We exploit the connection between the capacity of a transportation network and the amount of resources allocated to the rescue operation, and we introduce a new objective function for the problem of evacuation in a dynamic network. Given a network with known edge lengths and with a known number of evacuees located at the vertices, we would like to assign capacities to the edges of the network, from a fixed capacity budget, in such a way that the evacuation time of all evacuees to the set of fixed sink nodes in the network is minimized. We consider a simple path network with one fixed sink node and observe that the solution can be obtained numerically from a non‐linear program. However, by exploiting two useful properties of the optimal capacity allocation, we propose a combinatorial algorithm that returns a parametric solution, that is, a solution that depends on a single parameter, namely the capacity assigned to one edge of the path. Our algorithm runs in time where is the budgeted capacity, is the precision to which the solution is computed, and is the number of vertices occupied by evacuees in an ‐vertex path. This work is the first to consider the capacity allocation problem in the context of sink location problems.

We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).

Several authors have quantified the modularity of software systems in terms of coupling and cohesion metrics. Most of these approaches focus on functional and procedural dependencies in the system. Although highly relevant at the design phase, these static dependencies alone do not account for how a software product evolves over time. Instead, this is also dictated by logical and hidden dependencies between system files. To a large extent, the co-change (co-commit) relation captures these different types of dependencies. In this paper, we define two measures of co-change-modularity of a software product based on a weighted design structure matrix (DSM). The first metric, called the weighted propagation cost, uses matrix exponential to measure how changes to one system file potentially affect the whole product. The second metric, called the weighted clustering cost, uses the output of the first metric to measure the partitionability of the system based on the co-change relation. In addition, we provide a visual representation of how the co-change structure of a system evolves over time. We discuss the theoretical foundation of our work and highlight its advantages over existing methodologies. We apply our approach to GNU Octave and show the findings to be consistent with the available literature on the evolution of Octave. Our analysis is extensible and applicable to a range of scenarios including open source systems.

We study the task scheduling problem in vehicular clouds. Task scheduling in vehicular clouds must deal with the transient nature of the cloud resources and a relaxed definition of non-preemptive tasks. Despite a rich literature in machine scheduling and grid computing, this problem has not been examined yet. We show that even the problem of finding a minimum cost schedule for a single task over unrelated machines is NP-hard. We then provide a fully polynomial time approximation scheme and a greedy approximation for scheduling a single task. We extend these algorithms to the case of scheduling n tasks. We validate our algorithms through extensive simulations that use synthetically generated data as well as real data extracted from vehicle mobility and grid computing workload traces. Our contributions are, to the best of our knowledge, the first quantitative analysis of the computational power of vehicular clouds.

We consider the problem of allocating clients to base stations in wireless networks. Two design decisions are the location of the base stations, and the power levels of the base stations. We model the interference, due to the increased power usage resulting in greater serving radius, as capacities that are non-increasing with respect to the covering radius. Clients have demands that are not necessarily uniform and the capacity of a facility limits the total demand that can be served by the facility. We consider three models. In the first model, the location of the base stations and the clients are fixed, and the problem is to determine the serving radius for each base station so as to serve a set of clients with maximum total profit subject to the capacity constraints of the base stations. In the second model, each client has an associated demand in addition to its profit. A fixed number of facilities have to be opened from a candidate set of locations. The goal is to serve clients so as to maximize the profit subject to the capacity constraints. In the third model, the location and the serving radius of the base stations are to be determined. There are costs associated with opening the base stations, and the goal is to open a set of base stations of minimum total cost so as to serve the entire demand subject to the capacity constraints at the base stations. We show that for the first model the problem is NP-complete even when there are only two choices for the serving radius, and the capacities are 1,2. For the second model, we give a 1/2 approximation algorithm. For the third model, we give a column generation procedure for solving the standard linear programming model, and a randomized rounding procedure. We establish the efficacy of the column generation based rounding scheme on randomly generated instances.

Quality of service (QoS) in wireless mesh networks is an active area of research which is driven by the increasing demand for multimedia content delivered wirelessly. The IEEE 802.16 (WiMAX) standard identifies four classes of service targeting throughput, delay, and jitter. In this paper, we achieve two main objectives. (1) We present a routing metric sensitive to both interference and throughput which proves effective in QoS provisioning, a link scheduling algorithm that can easily accommodate all four classes of service by using the concept of feasible intervals, and an effective channel allocation algorithm inspired by a constraint programming heuristic. (2) We prove that the usual approach of constructing routing trees centred at the base station could lock significant network resources. By simply switching to a session based routing strategy, we illustrate that the acceptance ratio under a congested network can improve by more than 10% when compared to the tree based routing driven by our interference and throughput aware metric and by more than 25% when the routing tree is constructed with the metric sensitive to interference only.

Multihop cellular networks (MCNs) enhance the capacity and coverage and alleviate the dead-spot and hot-spot problems of cellular networks. They also allow faster and cheaper deployment of cellular networks. A fundamental issue of these networks is packet delay because multihop relaying for signals is involved. An effective channel assignment is the key to reducing delay. In this paper, we propose an optimal and a heuristic channel assignment scheme, called OCA and minimum slot waiting first (MSWF), respectively, for a time division duplex (TDD) wideband code division multiple access (W-CDMA) MCN. OCA provides an optimal solution in minimizing packet delay and can be used as an unbiased or benchmark tool for comparison among different network conditions or networking schemes. However, OCA is computationally expensive and, thus, inefficient for large real-time channel assignment problem. In this case, MSWF is more appropriate. Simulation results show that MSWF achieves on average 95 percent of the delay performance of OCA and is effective in achieving high throughput and low packet delay in conditions of different cell sizes.

Efficient and effective deployment of IEEE 802.16 networks to service an area of users with certain traffic demands is an important network planning problem. We resort to an evolutionary approach in order to yield good approximation solutions. In our method, novel genetic variation operations are proposed to incorporate the feature of this real-world application of evolutionary algorithm.

In 3G-based multihop cellular networks (MCNs), the cell size affects the cell capacity and the network reachability, which in turn affect the total demand of source nodes that can be served or the system throughput. Improper cell size assignment greatly affects the performance of the networks. To address the cell size issue, we recently proposed the optimal cell size (OCS) scheme to find optimal cell sizes to maximize the system throughput for a 3G TDD W-CDMA MCN. Although OCS provides an optimal cell size solution, it is computationally expensive. In this paper, we propose a heuristic cell size scheme, called Small Cell Size First (SCSF), which is more efficient and provides good results in terms of throughput compared to the optimal solutions provided by OCS. SCSF outperforms the fixed small cell size (SCS) multi-hop case when the network is sparse and the large cell size single-hop case regardless of the network density.

Abstract We consider a generalization of the median and center facility location problem called the collection depots facility location (CDFL) problem. We are given a set of client locations and a set of collection depots and we are required to find the placement for a certain number of facilities, so that the cost of dispatching a vehicle from a facility, to a client, to a collection depot, and back, is optimized for all clients. The CDFL center problem minimizes the cost of the most expensive vehicle tour among all clients, and the CDFL median problem minimizes the sum of the tour costs for all clients. We provide the first polynomial time algorithms to solve the 1 and k median problems in trees with time complexities O(n log n) and O(kn3), respectively, where n is the number of vertices in the tree. In contrast, a restricted version of the k‐median problem, where clients are given lists of allowed collection depots, is NP‐complete even for star graphs. We also give an optimal linear time algorithm to solve the discrete and continuous weighted 1‐center problem, improving on the O(n log n) result of Tamir and Halman [Discrete Optimization 2(2005), 168–184]. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

3G-based Multi-hop cellular networks (MCNs) inherit a special characteristic of 3G systems, namely the relationship between a cell's coverage and its capacity. At the planning stage, a cell may be statically set to have small coverage with high capacity, a large coverage with small capacity, or some other fixed settings in between. Such static settings, however, do not adapt to the projected dynamic nature of users in 3G-especially in an MCN environment. In this paper, we propose the Optimal Cell Size (OCS) scheme for a 3G TDD W-CDMA MCN multi-cell environment. Given the cell capacity function, users' distribution and demands, OCS yields optimal cell sizes that maximize the system throughput through balancing coverage and capacity. Not only can OCS cope with dynamic network conditions, but it can also be considered as an aid to the network planning process. To the best of our knowledge, this is the first multi-cell optimal cell size scheme in the context of MCNs.

A typical task in many applications for vehicular networks is to disseminate information to a subset of vehicles on a highway. In this work we describe a theoretical estimation for the average number of such independent tasks that can be sustained concomitantly in ad-hoc vehicular networks using contention free medium access and a fixed number of wireless channels. We call this measure the vehicle to vehicle (V2V) capacity of the network. Using our estimation, we perform an analysis of the V2V network capacity under different highway traffic conditions and scenarios. A surprising conclusion drawn is that congestion actually determines an increase in capacity. Based on these observations, we propose a simple strategy that can increase the capacity by filtering communication tasks with length greater than a certain threshold which can be determined numerically.

Wireless networks have made great gains in usability and popularity. However, inherent limitations on cell capacity and coverage still exist. There are also dead-spots and hotspots problems in these networks. Ad hoc multi-hop relaying enhances cell capacity and coverage, alleviates the dead-spots problem, and helps to ease congestion in hotspots. However, multi-hopping also increases packet delay. Effective channel assignment is key to reducing delay. Existing channel assignment schemes are heuristics and may not guarantee optimal solutions in terms of minimum delay. In this paper, we provide an optimal channel assignment (OCA) scheme for ad hoc TDD W-CDMA multi-hop cellular networks (MCN) to minimize packet delay. OCA can also be used as an un-biased tool for the comparison among different network topologies, network densities, and protocols. To the best of our knowledge, this is the first time that a minimum delay optimal channel assignment is proposed in a multi-hop cellular environment.

Many mission-critical applications of wireless sensor networks generate traffic that have a stringent delay requirement. In this paper, we study the effects of relaying delay- constrained traffic in a wireless sensor network according to two different strategies. The first strategy allows traffic splitting, in which data flow can be split and sent on multiple paths from the source to the destination. The second strategy disallows traffic splitting, in which data flow cannot be split and must be sent on a single path from the source to the destination. We present a model based on linear and integer linear programming for finding an optimal allocation of splittable and unsplittable traffic in a wireless sensor network, in which traffic is subject to soft delay constraints. The objective is to minimize the total energy consumption spent on communication and the penalty incurred from the violation of delay constraints. Based on this model, we perform an empirical analysis to quantify the performance gains and losses of a splittable and unsplittable traffic allocation strategy for wireless sensor networks with delay-constrained traffic. The experiment results show that splitting traffic does not provide a significant advantage in energy consumption, but can afford strategies for relaying data with a lower delay penalty.

Energy is often considered the primary resource constraint in a wireless sensor network. Compared to sensing and data processing, the cost of communication is among the highest in energy consumption. In this paper, we study the effects of relaying data in a wireless sensor network according to two different strategies. The first strategy allows traffic splitting, in which data can be sent on multiple paths from the source to the destination. The second strategy disallows traffic splitting, in which data must be sent on a single path from the source to the destination. We present algorithms based on linear and integer programming for finding an optimal allocation of splittable and unsplittable traffic in a wireless sensor network that minimizes total energy consumption. The technique provides optimal solutions, and can be used by designers of communication protocols to assess the energy efficiency of a data relaying scheme for a given network configuration. We also perform an empirical analysis to quantify the comparative performance gains and losses of a splittable and unsplittable traffic allocation strategy for wireless sensor networks. Results show that although the energy savings of a splittable traffic allocation strategy is relatively small when compared to the unsplittable case (on average, ranging from 0% to 1.82%), an allocation of splittable traffic can tolerate up to an additional 14.1% increase in network traffic load until any further load increase returns no feasible solutions.

Multi-hop relaying is an important concept in future generation wireless networks. It can address the inherent problems of limited capacity and coverage in cellular networks. However, most multi-hop relaying architectures are designed based on a small fixed-cell-size and a dense network. In a sparse network, the throughput and call acceptance ratio degrades because distant mobile nodes cannot reach the base station to use the available capacity. In addition, a fixed-cell-size cannot adapt to the dynamic changes of traffic pattern and network topology. In this paper, we propose a novel multi-hop relaying architecture called the adaptive multi-hop cellular architecture (AMC). AMC adapts the cell size to an optimal value that maximizes throughput by taking into account the dynamic changes of network density, traffic patterns, and network topology. To the best of our knowledge, this is the first time that adaptive (or optimal) cell size is accounted for in a multi-hop cellular environment. AMC also achieves the design goals of a good multi-hop relaying architecture. Simulation results show that AMC outperforms a fixed-cell-size multi-hop cellular architecture and a single-hop case in terms of data throughput, and call acceptance ratio

In this paper, the concern is with the management of data traffic after node deployment. To address some of the shortcomings of both single and multihop communication, this paper work with a hybrid model. The WSNet architecture is comprised of three classes of sensor nodes, sensors, relay nodes, and relay gateways. Sensors - gather and send data values to one relay nodes. Relay nodes - receive data values from sensors and/or other relay nodes and forward them to relay nodes or relay gateways. Relay gateways - receive data values from RN and send them directly (in one hop) to the base station, possibly using a dedicated channel. Our goal is to select paths along which data packets can be relayed until they reach one or more relay gateways while satisfying several constraints. These decisions take place at the application level, are computed by a central algorithm running at the base station, and rely on routing protocols to deliver the messages. A fixed topology of directly communicating nodes were assumed and a long term data communication plan based on knowing the amount of data generated by sensor nodes. The optimality of the solution obtained was guaranteed