An efficient heuristic algorithm for channel assignment problem incellular radio networks

This paper presents an efficient heuristic algorithm for the channel assignment problem in cellular radio networks. The task is to find channel assignment with minimum frequency bandwidth necessary to satisfy given demands from different nodes in a cellular network. At the same time the interference among calls within the same cell and from different neighboring cells are to be avoided, where interference is specified as the minimum frequency distance to be maintained between channels assigned to a pair of nodes. The simplest version of this problem, where only cochannel interferences are considered, is NP-complete. The proposed algorithm could generate a population of random valid solutions of the problem very fast. The best among them is the optimum or very near to optimum solution. For all problems with known optimal solutions, the algorithm could find them. A statistical estimation of the performance of the proposed algorithm is done. Comparison with other methods show that our algorithm works better than the algorithms that we have investigated     

An efficient channel assignment algorithm for multicast wireless mesh networks

Multicast can enhance the performance of wireless mesh networks (WMNs) effectively, which has attracted great attentions in recent years. However, multicast communication in WMNs requires efficient channel assignment strategy to reduce the total network interference and maximize the network throughput. In this paper, the concept of local multicast is proposed to measure interference and solve hidden channel problem in multicast communication. Basing on the concept, we propose a channel assignment algorithm considering the interference of local multicast and forwarding weight of each node (LMFW). The algorithm fully considers partially overlapped channels and orthogonal channels to improve the network performance. Simulations show that the proposed algorithm can reduce interference and improve network capacity of WMNs.     

An efficient algorithm for solving Zakharov-Shabat inversescattering problem

An efficient numerical method for solving Zakharov-Shabat (ZS) inverse scattering problem is presented. In this method, instead of equivalent second-order differential equations to the Gel'fand-Levitan-Marchenko (GLM)-type integral equations, equivalent first-order differential equations are adopted and sufficiently accurate solutions to Zakharov-Shabat inverse problem can be achieved without iterations. Examples for applying it to design nonuniform transmission line (NTL) filters are also provided     

An efficient terminal and model order reduction algorithm

The paper proposes an efficient terminal and model order reduction method for compact modeling of interconnect circuits with many terminals. The new method is inspired by the recently proposed terminal reduction method, SVDMOR [P. Feldmann, F. Liu, Sparse and efficient reduced order modeling of linear subcircuits with large number of terminals, in: Proceedings of the International Conference on Computer Aided Design (ICCAD), 2004, pp. 88-92]. But different from SVDMOR, the new method considers higher order moment information for terminal responses during the terminal reduction and separately applies singular value decomposition (SVD) on both input and output terminals for low-rank approximations. This is in contrast to the SVDMOR method where input and output terminal responses are approximated by SVD at the same time, which can lead to large errors when the numbers of inputs and outputs are quite different. We analyze the passivity requirements for SVD-based terminal and model order reduction and show that the combined passive terminal and MOR using SVD method will not lead an effective terminal reduction in general. Our experimental results show that the proposed ESVDMOR method outperforms the SVDMOR method in terms of accuracy for the same reduced model sizes when the numbers of input and output terminals are quite different.     

一个基于动态带宽分配有效实时磁盘调度算法

多媒体服务器需要一个实时磁盘调度算法为具有软实时要求的连续多媒体流服务。传统的磁盘调度算法不适应实时多媒体流。提出一个新的实时磁盘调度DBA-SCAN（Dynamic-Band-width-Assignment-SCAN）算法。DBA-SCAN算法通过带宽预留和接纳控制机制为处于服务中多媒体流提供质量保证。对于非实时任务也预留了带宽以保证非实时任务具有合理的响应时间。DBA-SCAN采用一种积极策略在运行时动态回收未用的带宽。被回收的带宽被用于为可选任务或者更多的非实时任务服务。通过模拟实验对DBA-SCAN算法和WRR-SCAN算法进行对比,实验结果显示,DBA-SCAN为实时多媒体流提供了更好的质量。     

An efficient algorithm for determination of the optimum base-station assignment in cellular DS-CDMA systems

An algorithm is proposed that finds the optimum assignment of mobile users to base stations, and its associated transmission powers, in a cellular direct-sequence code-division multiple-access network, with a computational complexity that grows polynomially with the number of users and base stations. The algorithm detects infeasible situations and allows the inclusion of power constraints. Its performance is analyzed in terms of complexity and system capacity.     

一个优化的低阶多项式累加和问题求解算法

本文针对低阶多项的多项式累加和问题∑n k=1 f(k),其中f(x)=c0+c1 x+…+cm-1 xm-1+cm xm,当多项式幂次m较小,累加项数n较大的情况下,根据二分求解思想,设计了一种高效的递推求解方法,其时间复杂度为O(m2 log n),而采用Horner格式计算多项式在每点的取值,再进行累加的朴素算法时间复杂度为O(mn),从而解决了在n>>m时,大大提高了低阶多项的多项式累加求和的效率.     

An efficient Krylov-subspace-based algorithm to solve thedielectric-waveguide problem

An efficient scheme based on the bi-Lanczos algorithm has been developed for analysis of the dielectric-waveguide problem. A two-dimensional finite-difference scheme in the frequency domain is used to discretize the waveguide cross section. The resulting sparse eigenvalue problem is solved efficiently using the bi-Lanczos algorithm. Apart from solving the modes of the dielectric waveguide, a scheme to solve for the fields in the presence of a localized source is also described. Numerical results are also included to confirm the validity of the method     

An energy efficient channel assignment and routing algorithm for multi-radio wireless mesh networks

Endowing mesh routers with multiple radios is a recent solution to improve the performance of wireless mesh networks. Solving the problem how to assign channels to radios has attracted a lot of attention in the recent years, partly because of the hardness of solving the channel assignment problem jointly with the routing problem. However, the approaches proposed in the literature so far have mainly focused on reducing interference or maximizing the throughput. Little attention has been paid to the energy consumption of wireless mesh networks, given that mesh nodes are usually connected to a power source. However, with the rising concerns about the energy consumed by communication infrastructures, it makes sense to consider the minimization of the energy consumption as an objective of the channel assignment and routing problem. Our work stems from the observation that an idle radio simply overhearing a frame consumes nearly the same power as the radio actually receiving the frame. Hence, energy may be saved by turning off a number of radios, if the performance of the network is not impaired. In this paper, we define the energy efficient channel assignment and routing problem, show that it is NP-hard and propose a heuristic algorithm. For the purpose of comparing the solution found by the proposed algorithm to the optimal solution, we also present two Mixed Integer Linear Programs (MILPs) that optimally solve the problem we address. Finally, we show the results of extensive simulation studies we conducted to assess the effectiveness of the proposed algorithm.     

An efficient algorithm for the link allocation problem on ATM-basedpersonal communication networks

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     

An efficient heuristic waveband assignment algorithm for hierarchical optical path networks utilizing wavelength convertors

We propose a hierarchical optical path network design algorithm that allows for wavelength conversion. The algorithm sequentially solves a set of sub-problems that result from decomposing the original design problem. A novel efficient heuristic is developed to solve the waveband assignment sub-problem that is the bottleneck among the sub-problems. Numerical experiments prove that, by employing wavelength conversion, hierarchical optical path networks will be more cost effective than the single layer optical path network even in the small traffic demand area, where cost-effectiveness cannot be realized without using wavelength conversion, as well as in the relatively large traffic demand area.     

解决频率指配问题的蚁群算法

将蚁群算法和经典的四级预测模型结合使用,解决了大规模电台数目电子信息系统的频率指配问题.此类问题的数学模型与传统问题不同.提出针对该问题的算法性能评估准则,并研究了各参数对算法性能的影响.依据对研究结果的分析,提出优化参数的设定准则.     

A load balancing energy efficient clustering algorithm for MANETs

Nodes in mobile ad hoc Networks (MANETs) are characterized by their limited resources. Hence, the concept of clustering was introduced to allow spacial reuse of bandwidth and to minimize routing overhead. However, node mobility perturbs the stability of the network and affects the performance of other protocols such as scheduling, routing, and resource allocation, which makes re‐clustering the network to maintain up‐to‐date information at each node unavoidable. Consequently, clustering models for MANETS should be carefully designed while taking into consideration the fact that mobile nodes are energy constrained. In this paper, we propose a dynamic energy‐efficient clustering algorithm that prolongs the network lifetime by electing cluster‐heads taking into consideration, in addition to other parameters such as mobility, their residual energies and making them dynamically monitor their energy consumption to either diminish the number of their cluster‐members or relinquish their roles. We have evaluated the performance of the proposed clustering model and compared it with other related clustering approaches found in the literature. Obtained results show the efficiency of the proposed algorithm. Copyright © 2010 John Wiley & Sons, Ltd.     

An efficient borrowing channel assignment scheme for cellularmobile systems

In this paper, we propose a new efficient borrowing channel assignment (BCA) scheme, which consists of two phases. The first ordinary channel allocation phase borrows a channel from neighboring cells by an impact-based borrowing strategy. The second channel reallocation phase has a reallocation procedure for locked-channel utilization and a reallocation procedure for efficient channel reuse. Simulation results show that in both uniform and nonuniform traffic cases, our schemes significantly reduce the system blocking probability over the other existing schemes. Furthermore, one of our schemes has a much smaller number of reallocations than other compared schemes     

Hungarian algorithm for subcarrier assignment problem using GPU and CUDA

General purpose graphics processing units (GPGPUs) have gained much popularity in scientific computing to speedup computational intensive workloads. Resource allocation in terms of power and subcarriers assignment, in current wireless standards, is one of the challenging problems due to its high computational complexity requirement. The Hungarian algorithm (HA), which has been extensively applied to linear assignment problems (LAPs), has been seen to provide encouraging result in resource allocation for wireless communication systems. This paper presents a compute unified device architecture (CUDA) implementation of the HA on graphics processing unit (GPU) for this problem. HA has been implemented on a parallel architecture to solve the subcarrier assignment problem and maximize spectral efficiency. The proposed implementation is achieved by using the “Kuhn‐Munkres” algorithm with effective modifications, in order to fully exploit the capabilities of modern GPU devices. A cost matrix for maximum assignment has been defined leading to a low complexity matrix compression along with highly optimized CUDA reduction and parallel alternating path search process. All these optimizations lead to an efficient implementation with superior performance when compared with existing parallel implementations.     

An efficient data collection and load balance algorithm in wireless sensor networks

The nature of multi-hop data transmission in wireless sensor network will cause serious load unbalance which will produce great restrains in related applications considering the limited energy resource. Relative load balance algorithms are usually performed inside the clusters without considering about the energy consumption of the whole network. A cluster-based balanced energy consumption algorithm (BECA) is proposed by introducing in multiple inter-cluster links to distribute the load, so as to achieve global load balance. Moreover, an efficient data collecting mechanism is proposed based on BECA to improve the traffic balance further. Simulating results based on NS2 show that BECA can obtain better balance properties and prolong the network lifetime effectively.

     

An adaptive link assignment algorithm for dynamically changingtopologies

An adaptive link assignment algorithm for the distributed optimization of dynamically changing network topologies is presented. The algorithm is responsible for determining the network connectivity by controlling the selection of links to be established and disconnected. This algorithm is designed to recover from predictable link outages as well as massive unpredictable failures. To minimize computational time complexity as well as to improve transient response. Some known graph-theoretic algorithms are utilized     

An approach to minimum cost steel rolling

A metal rolling process is examined, and shown to be an implicit, discrete, multistage, control process with admissible control set dependent only upon the system state. By means of numerical techniques, dynamic programming is applied to this process to generate a closed-loop roll setting policy which is optimal in the sense that it achieves a specified final state at minimum dollar cost. Digital simulation and Monte Carlo techniques are used to compare performance of the optimally controlled mill with that of the the same mill, operating in accord with current rolling practices. Both models are examined using random initial conditions and the process sensors are assumed to contribute noise to the measurement of the system state. An averaging technique is used to decrease the effects of this noise on system performance.     

A fast general slew constrained minimum cost buffering algorithm

As VLSI technology moves to the nanoscale regime, ultra-fast slew buffering techniques considering buffer cost minimization are highly desirable. The existing technique proposed in [S. Hu, C. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi, C.-N. Sze, Fast algorithms for slew constrained minimum cost buffering, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26 (11) (2007) 2009-2022] is able to efficiently perform buffer insertion with a simplified assumption on buffer input slew. However, when handling more general cases without input slew assumptions, it becomes slow despite the significant buffer savings. In this paper, a fast buffering technique is proposed to handle the general slew buffering problem. Instead of building solutions from scratch, the new technique efficiently optimizes buffering solutions obtained with the fixed input slew assumption. Experiments on industrial nets demonstrate that our algorithm is highly efficient. Compared to the commonly used van Ginneken style buffering, up to 49× speed up is obtained and often 10% buffer area is saved. Compared to the algorithm without input slew assumption proposed in [S. Hu, C. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi, C.-N. Sze, Fast algorithms for slew constrained minimum cost buffering, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26 (11) (2007) 2009-2022], up to 37× speedup can be obtained with slight sacrifice in solution quality.     

An efficient method for terminal and multiterminal pathset enumeration

The literature is abundant with algorithms for determining separately the paths for the single terminal pair, paths for multiterminal pairs and cuts for a specified terminal pair of any network, from knowledge of the reliability logic diagram (RLD). However, very few methods are available as efficient algorithms for enumerating simultaneously the paths between any single terminal pair, paths for multiterminal pairs and cuts for the specified terminal pair.The present paper provides a conceptually simple and computationally efficient algorithm to obtain simultaneously the paths between any single pair of terminals, paths for multiterminal pairs and the cuts for the specified terminal pair of interest of any complex network. The algorithm is easy and computationally economical and also applicable to graphs having both nodes and branches of finite non-zero failure probability.An illustrative example is provided to demonstrate the effectiveness of the proposed algorithm.