In order to support transmissions of multimedia data (high data rate and burst) with performance guarantees in a wideband CDMA system, it is crucial to design a judicious algorithm for burst data admission control and...
详细信息
In order to support transmissions of multimedia data (high data rate and burst) with performance guarantees in a wideband CDMA system, it is crucial to design a judicious algorithm for burst data admission control and scheduling. However, in the current literature there are only simple techniques (such as first-come-first-served and equal sharing) suggested for tackling the problem. Indeed, these existing schemes are not designed for optimizing the precious bandwidth resources while providing performance guarantees (e.g., a user admitted with a certain data rate can enjoy the assigned rate without interruption). In this paper, we first present our novel integer programming formulation of the burst data admission control and scheduling problem. The objective of the optimization can be maximizing the utilization of the bandwidth resources or minimizing the delays of the user transmissions. Taking into account all the important factors such as mobility, power control, and soft handoff, our formulation induces an algorithm for generating an optimal admission control solution which consists of: (1) the burst data rate (in terms of the number of channels);(2) the burst duration;and (3) the burst start time. For practical implementation, we also suggest a near-optimal version of the algorithm, which is evaluated via static and dynamic simulations, and comparisons with two existing schemes.
To effectively balance contradiction between sensing time of access channel and total throughput of channel in secondary user system of cognitive wireless network, a kind of spectrum access strategy sensing part of ch...
详细信息
To effectively balance contradiction between sensing time of access channel and total throughput of channel in secondary user system of cognitive wireless network, a kind of spectrum access strategy sensing part of channels is proposed. The Thesis, based on algorithm proposed through single secondary user carrying out transmission on multiple channels of master user at the same time, takes total throughout of channel as objective function;on one hand, it is related to transmission rate, on the other hand, it is related to selection of sensing time and sensing channel. The algorithm assumes secondary user detects channel through perception in order and chooses certain suitable channel by using optimum stopping theory to perceive. It avoids sensing all channels, meanwhile, the throughput is greater. Through comparison with simulation analysis of HC-MAC (Hardware-constrained Cognitive MAC) algorithm, the algorithm avoids sensing all channels and lowers expenditure, meanwhile, the throughput is greater, which make it obtain obvious advantage on performance.
作者：
COLE, RJDep. Comp. Sci.
Courant Inst. Math. Sci. New York Univ. 251 Mercer St. New York NY 10012 USA
The author gives an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log*n) time. A modification of the algorithm runs on the CRCW PRAM. It r...
详细信息
The author gives an optimally efficient parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log*n) time. A modification of the algorithm runs on the CRCW PRAM. It requires a linear number of operations and O(log n log*n/log log n) time.
The computational time of an absolute comparison recognizer is a random variable related to a measure of computational length. These variables depend on the choice of an algorithm which carries out the recognition. Th...
详细信息
The computational time of an absolute comparison recognizer is a random variable related to a measure of computational length. These variables depend on the choice of an algorithm which carries out the recognition. The expectation and the variance of the computational length are examined in detail with reference to the probability distribution of the classes to be discriminated. In particular, upper and lower bounds of the smallest mean computational length are found in easily evaluable forms.
A single-machine scheduling problem with preemptive jobs and workload-dependent maintenance durations is considered. The length of a maintenance duration is modeled as an non-negative increasing function of the total ...
详细信息
A single-machine scheduling problem with preemptive jobs and workload-dependent maintenance durations is considered. The length of a maintenance duration is modeled as an non-negative increasing function of the total processing time of the jobs scheduled between the current maintenance and the latest previous one. The objective is to minimize the makespan. Two optimal algorithms are proposed for the case where the maintenance duration function is convex and the case where the maintenance duration function is concave, respectively.
The Voronoi diagram of a finite set S of points in the Euclidean plane is a well-known geometric model useful for applications in various areas of science. A new and optimal algorithm is outlined for computing collin...
详细信息
The Voronoi diagram of a finite set S of points in the Euclidean plane is a well-known geometric model useful for applications in various areas of science. A new and optimal algorithm is outlined for computing collinear weighted Voronoi diagrams (WVD) that is conceptually simpler and appears very attractive for practical implementations. The approach is based on 2-dimensional interpretation of the diagram. This interpretation also permits the establishment of exact upper bounds on the number of components realized by the diagram. It is believed that, as for the planar diagram, the optimal algorithm for collinear WVDs is of merit to several areas of science outside computer science.
The notion of a Towers of Hanoi contest is introduced and the complexity of some adjudication methods are investigated. We present linear time and space adjudication algorithms, that is optimal adjudication algorithms.
The notion of a Towers of Hanoi contest is introduced and the complexity of some adjudication methods are investigated. We present linear time and space adjudication algorithms, that is optimal adjudication algorithms.
Elevation gradients are primary components of slope and aspect. Significant concerns remain when computing gradients if noise (perturbing non-DEM data) is present. There is still a need to find ways to balance accurac...
详细信息
Elevation gradients are primary components of slope and aspect. Significant concerns remain when computing gradients if noise (perturbing non-DEM data) is present. There is still a need to find ways to balance accuracy of the gradient and stability to noise for specific types of DEM. In this study, six algorithms are compared using four DEMs and analyzed for stability to base level DEM noise and added random noise. Theoretical stability and accuracy of the formulae are analyzed using harmonic (frequency or spatial scale) response. The results provide a basis to determine the most appropriate algorithm for different situations. They show that: (1) the set (Evans-Young (EY), Sharpnack (Sp), Sobel (Sb)) has a better stability to noise ratio than the set (Zevenbergen (Z), Florinsky (F), Horn (H)). EY has the smoothest surface and the highest stability to noise ratio. If stability is the primary measure in mid-frequencies, EY is a good choice. (2) Sb is good because of its accuracy in mid to high frequencies. Out to the highest frequencies, Sb is the best. (3) F has potential but should not be used with very high-frequency noise. (4) H and Z should not be used when there is substantial noise.
We explore two motion planning problems where a group of mobile robots has to reach a target located in an a priori unknown environment while on-line planning the next step. In the first problem the target position is...
详细信息
We explore two motion planning problems where a group of mobile robots has to reach a target located in an a priori unknown environment while on-line planning the next step. In the first problem the target position is unknown and should be found by the robots, while in the second problem the target position is known and only a path to it should be found. We focus on optimizing the cost of the task in terms of motion time, which, under the assumption of uniform velocity of all the robots, correlates to the path length passed by the robot which reaches the target. The performance of an on-line algorithm is usually expressed in terms of Competitiveness, the constant ratio between the on-line and the optimal off-line solutions. Specifically, the ratio between the lengths of the actual path made by the robot which reached the target to the shortest path to the target. We use generalized competitiveness, i.e., the ratio is not necessarily constant, but could be any function. Classification of a motion planning task in the sense of performance is done by finding an upper and a lower bounds on the competitiveness of all algorithms solving that task. If the two bounds belong to the same functional class this is the Competitive Complexity Class of the task. We find the two bounds for the aforementioned common on-line motion planning problems, and classify them into competitive classes. It is shown that in general any on-line motion planning algorithm that tries to solve these problems must have at least a quadratic competitive performance. This is a lower bound of the problems. This paper describes two new on-line navigation algorithm which solve the problems under discussion. The first is called MRSAM, short for Multi-Robot Search Area Multiplication, and the second is called MRBUG, short for Multi-Robot BUG which extends Lumelsky famous BUG algorithm. Both algorithms have quadratic upper bounds, which prove that the problems they solve have quadratic upper bounds. Thus it i
暂无评论