共查询到20条相似文献,搜索用时 0 毫秒
1.
This paper presents some algorithmic results concerning virtual path layouts for the one-to-many communication problem in ATM tree networks. The ATM network model is based on covering the network with a layout of virtual paths, under some constraints on the allowed load, namely, the number of paths that can share an edge. The quality measure used is the hop count, namely, the number of edges traversed between two vertices that need to communicate. Whereas most former results concerned the maximum hop count of the virtual path layout, our interest here is in measuring its total hop count, or alternatively its average hop count. The paper presents a dynamic programming algorithm for planning ATM network layouts with minimal total hop count for one-to-many requirements under load constraints over the class of tree networks. 相似文献
2.
In an ATM network, bandwidth is allocated at different levels and in different stages. At the physical level, the ATM topology can be dynamically reconfigured by adding/removing truns between ATM switches. This allocation of bandwidth is made possible by the SONET Synchronous Transfer Mode (STM) infrastructure equipped with Digital Cross Connect Systems (DCSs). We will refer to this allocation asSTM allocation. At the ATM level, we can allocate bandwidth to individual Virtual Circuits (ATM-VC allocation) as well as to Virtual Paths (ATM-VP allocation). For example, in order to implement the Connectionless Network Access layer functions we find it convenient to organize the Virtual Paths in a Connectionless Overlay Network. This introduces another type of bandwidth allocation (CLS allocation). In this paper, we address and formulate the above bandwidth allocation problems, and propose efficient techniques for their solution. We illustrate these techniques with examples based on STM and CLS allocation, respectively.This work was jointly supported by the Brazilian National Science Council (CNPq) and NSF. 相似文献
3.
Motivated by ABR class of service in ATM networks, we study a continuous time queueing system with a feedback control of the
arrival rate of some of the sources. The feedback about the queue length or the total workload is provided at regular intervals
(variations on it, especially the traffic management specification TM 4.0, are also considered). The propagation delays can
be nonnegligible. For a general class of feedback algorithms, we obtain the stability of the system in the presence of one
or more bottleneck nodes in the virtual circuit. Our system is general enough that it can be useful to study feedback control
in other network protocols. We also obtain rates of convergence to the stationary distributions and finiteness of moments.
For the single botterneck case, we provide algorithms to compute the stationary distributions and the moments of the sojourn
times in different sets of states. We also show analytically (by showing continuity of stationary distributions and moments)
that for small propagation delays, we can provide feedback algorithms which have higher mean throughput, lower probability
of overflow and lower delay jitter than any open loop policy. Finally these results are supplemented by some computational
results.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
4.
The goal of this paper is to recommend a good Private Network-to-Network Interface (PNNI) routing algorithm for private ATM networks. A good routing algorithm has to work well with multimedia traffic with several quality of service (QoS) requirements (such as cell loss ratio, cell delay and its variation etc.) in different networks under various traffic conditions. The multiplicity of QoS requirements makes the routing problem NP-complete, so our approach to the problem is based on large scale simulations involving several empirical algorithms (compliant with the PNNI routing specification) which have been tested for different network topologies and traffic scenarios. Based on analysis of tradeoffs involving performance metrics (such as blocking rate, complexity, load distribution) we recommend a consistently good routing algorithm for single domain ATM networks. 相似文献
5.
6.
A state variable mathematical model for use in the synthesis of automatic control systems for open-channel networks is presented. The system considered here consists of n-cascaded reaches joined by control gates.The linear time invariant model consists of a controllable and observable representation where the state variables are the stored water volume variations in each reach and the control signals are the variations of the control gates opening sections. The model derives, through appropriate simplifications, from a more complex one in terms of transfer functions which was derived by linearizing the Saint-Venant equations.The problem of a linear quadratic optimal regulator is formulated in classical terms for the canal system and the constant-volume control laws obtained for the simplified model have been imposed on the complex one: such a control is therefore to be considered sub-optimal.The results of a digital simulation of the controlled system behaviour indicate that the system operates with practically constant stored water volumes in each reach and that such behaviour is fairly close to that of a pressure-water pipe system. 相似文献
7.
We study a combinatorial geometric problem related to the design of wireless networks with directional antennas. Specifically, we are interested in necessary and sufficient conditions on such antennas that enable one to build a connected communication network, and in efficient algorithms for building such networks when possible.We formulate the problem by a set P of n points in the plane, indicating the positions of n transceivers. Each point is equipped with an α-degree directional antenna, and one needs to adjust the antennas (represented as wedges), by specifying their directions, so that the resulting (undirected) communication graph G is connected. (Two points p,q∈P are connected by an edge in G, if and only if q lies in p?s wedge and p lies in q?s wedge.) We prove that if α=60°, then it is always possible to adjust the wedges so that G is connected, and that α?60° is sometimes necessary to achieve this. Our proof is constructive and yields an time algorithm for adjusting the wedges, where k is the size of the convex hull of P.Sometimes it is desirable that the communication graph G contain a Hamiltonian path. By a result of Fekete and Woeginger (1997) [8], if α=90°, then it is always possible to adjust the wedges so that G contains a Hamiltonian path. We give an alternative proof to this, which is interesting, since it produces paths of a different nature than those produced by the construction of Fekete and Woeginger. We also show that for any n and ε>0, there exist sets of points such that G cannot contain a Hamiltonian path if α=90°−ε. 相似文献
8.
9.
Vidyadhar G. Kulkarni 《Operations Research Letters》1984,3(3):137-140
This paper presents a method of identifying all directed paths from the source to the sink (called ‘paths’ in this paper) in a directed acyclic network with one source and one sink. Let L be the set of all the paths in this network and N = |L|. A hash function H:L → {0, 1, …, N ? 1} is constructed having the following properties: it is one-to-one and onto, the algorithms to compute H and its inverse are linea in the number of arcs in the network, it has the smallest possible range and produces no collisions. All these properties make it a very useful hash function in writing computer programs which involve storing information about all paths in the network. The techniques described in this paper can be used to construct hash functions for walks in cyclic graphs. An application to simulation of stochastic networks is described and an illustrative example is included. 相似文献
10.
Yehuda Ben-Shimol Boaz Ben-Moshe Yoav Ben-Yehezkel Amit Dvir Michael Segal 《Journal of Heuristics》2007,13(3):243-263
This article addresses a real-life problem - obtaining communication links between multiple base station sites, by positioning
a minimal set of fixed-access relay antenna sites on a given terrain. Reducing the number of relay antenna sites is considered
critical due to substantial installation and maintenance costs. Despite the significant cost saved by eliminating even a single
antenna site, an inefficient manual approach is employed due to the computational complexity of the problem. From the theoretical
point of view we show that this problem is not only NP hard, but also does not have a constant approximation. In this paper
we suggest several alternative automated heuristics, relying on terrain preprocessing to find educated potential points for
positioning relay stations. A large-scale computer-based experiment consisting of approximately 7,000 different scenarios
was conducted. The quality of alternative solutions was compared by isolating and displaying factors that were found to affect
the standard deviation of the solutions supplied by the tested heuristics. The results of the simulation based experiments
show that the saving potential increases when more base stations are needed to be interconnected. The designs of a human expert
were compared to the automatically generated solutions for a small subset of the experiment scenarios. Our studies indicate
that for small networks (e.g., connecting up to ten base stations), the results obtained by human experts are adequate although
they rarely exceed the quality of automated alternatives. However, the process of obtaining these results in comparison to
automated heuristics is longer. In addition, when more base station sites need to be interconnected, the human approach is
easily outperformed by our heuristics, both in terms of better results (fewer antennas) and in significant shorter calculation
times. 相似文献
11.
In this paper we review and extend the effective bandwidth results of Kelly [28], and Kesidis, Walrand and Chang [29, 6]. These results provide a framework for call admission schemes which are sensitive to constraints on the mean delay or the tail distribution of the workload in buffered queues. We present results which are valid for a wide variety of traffic streams and discuss their applicability for traffic management in ATM networks. We discuss the impact of traffic policing schemes, such as thresholding and filtering, on the effective bandwidth of sources. Finally we discuss effective bandwidth results for Brownian traffic models for which explicit results reveal the interaction arising in finite buffers. 相似文献
12.
Motivated by topology control in ad hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). The input consists of a directed complete weighted digraph G=(V,c) (that is, ). The power of a vertex u in a directed spanning subgraph H is given by , and corresponds to the energy consumption required for node u to transmit to all nodes v with uv∈E(H). The power of H is given by . Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer d and a r∈V. The output H must be a r-rooted outgoing arborescence of depth at most d. We give an (O(logn),O(logn)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn) and power at most O(logn) times the optimum solution.For the Euclidean case, when c(u,v)=c(v,u)=∥u,v∥κ (here ∥u,v∥ is the Euclidean distance and κ is a constant between 2 and 5), the output of our algorithm can be modified to give a O((logn)κ) approximation ratio. Previous results for Min-Power Bounded-Hops Broadcast are only exact algorithms based on dynamic programming for the case when the nodes lie on the line and c(u,v)=c(v,u)=∥u,v∥κ.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where H must have a path of at most d edges in between any two nodes. Previous work for Min-Power Bounded-Hops Strong Connectivity consists only of constant or better approximation for special cases of the Euclidean case. 相似文献
13.
Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ). 相似文献
14.
A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648(rmax/rmin)^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most (1 + 2rmax/rmin)^2+32, Moreover, under the proposed scheduling each node just needs to forward a message at most once. 相似文献
15.
We formulate a model for the optimal location of switches in ATM communications networks. The networks are designed in such a way that, at their arrival to the switches, ATM cells find free space in a buffer of length b, with a probability α. The model avoids the impairment to the communication caused by both cell loss (because of shorter buffers) and cell-delay variations (because of longer buffers). It is also shown how to transform a non-linear, probabilistic, constraint into a linear form. Computational experience is provided for the model. This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
16.
In this paper we study a new variant of the minimum energy broadcast (MEB) problem, namely the probabilistic MEB (PMEB). The objective of the classic MEB problem is to assign transmission powers to the nodes of a wireless network is such a way that the total energy dissipated on the network is minimized, while a connected broadcasting structure is guaranteed by the assigned transmission powers. In the new variant of the problem treated in this paper, node failure is taken into account, aiming at providing solutions with a chosen reliability level for the broadcasting structure. Three mixed integer linear programming formulations for the new problem are presented, together with efficient formulation-dependent methods for their solution. Computational results are proposed and discussed. One method emerges as the most promising one under realistic settings. It is able to handle problems with up to fifty nodes. 相似文献
17.
Fabian Castaño Eric Bourreau Nubia Velasco André Rossi Marc Sevaux 《European Journal of Operational Research》2015
In this paper, we consider the duty scheduling of sensor activities in wireless sensor networks to maximize the lifetime. We address full target coverage problems contemplating sensors used for sensing data and transmit it to the base station through multi-hop communication as well as sensors used only for communication purposes. Subsets of sensors (also called covers) are generated. Those covers are able to satisfy the coverage requirements as well as the connection to the base station. Thus, maximum lifetime can be obtained by identifying the optimal covers and allocate them an operation time. The problem is solved through a column generation approach decomposed in a master problem used to allocate the optimal time interval during which covers are used and in a pricing subproblem used to identify the covers leading to maximum lifetime. Additionally, Branch-and-Cut based on Benders’ decomposition and constraint programming approaches are used to solve the pricing subproblem. The approach is tested on randomly generated instances. The computational results demonstrate the efficiency of the proposed approach to solve the maximum network lifetime problem in wireless sensor networks with up to 500 sensors. 相似文献
18.
A slotted ring that allows simultaneous transmissions of messages by different users is considered. Such a ring network is commonly called ring withspatial reuse. It can achieve significantly higher throughput than standard token rings but it also raises the issue of fairness since some nodes may be prevented from accessing the ring for long time intervals. Policies that operate in cycles and guarantee that a certain number (quota) of packets will be transmitted by every node in every cycle have been considered before to deal with the fairness issue. In this paper we address the problem of designing a policy that results in a stable system whenever the end-to-end arrival rates are within the stability region of the ring with spatial reuse (the stability region of the ring is defined as the set of end-to-end arrival rates for which there is a policy that makes the ring stable). We provide such a policy, which does not require knowledge of end-to-end arrival rates. The policy is an adaptive version of the quota policies and can be implemented with the same distributed mechanism. We use the Lyapunov test function technique together with methods from the theory of regenerative processes to derive our main results.This research was primarily done while the author was visiting INRIA in Rocquencourt, France. The author wishes to thank INRIA (projects ALGO, MEVAL and REFLECS) for a generous support. Additional support was provided by NSF Grants NCR-9206315 and CCR-9201078 and INT-8912631, and by Grant AFOSR-90-0107, and in part by NATO Grant 0057/89.The research of this author was supported in part by NSF under Grants NCR-9211417 and NCR-9406415, and by the New York State Center for Advanced Technology in Telecommunications, Polytechnic University. 相似文献
19.
Kamini Venkatesh Vadlamani Ravi Anita Prinzie Dirk Van den Poel 《European Journal of Operational Research》2014
To improve ATMs’ cash demand forecasts, this paper advocates the prediction of cash demand for groups of ATMs with similar day-of-the week cash demand patterns. We first clustered ATM centers into ATM clusters having similar day-of-the week withdrawal patterns. To retrieve “day-of-the-week” withdrawal seasonality parameters (effect of a Monday, etc.) we built a time series model for each ATMs. For clustering, the succession of seven continuous daily withdrawal seasonality parameters of ATMs is discretized. Next, the similarity between the different ATMs’ discretized daily withdrawal seasonality sequence is measured by the Sequence Alignment Method (SAM). For each cluster of ATMs, four neural networks viz., general regression neural network (GRNN), multi layer feed forward neural network (MLFF), group method of data handling (GMDH) and wavelet neural network (WNN) are built to predict an ATM center’s cash demand. The proposed methodology is applied on the NN5 competition dataset. We observed that GRNN yielded the best result of 18.44% symmetric mean absolute percentage error (SMAPE), which is better than the result of Andrawis, Atiya, and El-Shishiny (2011). This is due to clustering followed by a forecasting phase. Further, the proposed approach yielded much smaller SMAPE values than the approach of direct prediction on the entire sample without clustering. From a managerial perspective, the clusterwise cash demand forecast helps the bank’s top management to design similar cash replenishment plans for all the ATMs in the same cluster. This cluster-level replenishment plans could result in saving huge operational costs for ATMs operating in a similar geographical region. 相似文献
20.
Relund Nielsen Lars; Allan Andersen Kim; Pretolani Daniele 《IMA Journal of Management Mathematics》2003,14(3):271-303
In relevant application areas, such as transportation and telecommunications,there has recently been a growing focus on random time-dependentnetworks (RTDNs), where arc lengths are represented by time-dependentdiscrete random variables. In such networks, an optimal routingpolicy does not necessarily correspond to a path, but ratherto an adaptive strategy. Finding an optimal strategy reducesto a shortest hyperpath problem that can be solved quite efficiently. The bicriterion shortest path problem, i.e. the problem offinding the set of efficient paths, has been extensively studiedfor many years. Recently, extensions to RTDNs have been investigated.However, no attempt has been made to study bicriterion strategies.This is the aim of this paper. Here we model bicriterion strategy problems in terms of bicriterionshortest hyperpaths, and we devise an algorithm for enumeratingthe set of efficient hyperpaths. Since the computational effortrequired for a complete enumeration may be prohibitive, we proposesome heuristic methods to generate a subset of the efficientsolutions. Different criteria are considered, such as expectedor maximum travel time or cost; a computational experience isreported. 相似文献