Nature-inspired optimization of Moving Access Point-based radio networks

Wireless communication systems have penetrated into almost all parts of human life. They have become essential and pervasive and do affect both personal and professional aspects of our lives. While most types of wireless networks, such as cellular mobile communication networks, have been exhaustively studied and optimized, in order to handle various situations, there are also contexts which require efficient handling, e.g., moving hotspots, areas that have lost their infrastructure, and areas with hard morphology. The motivation for this work is the efficient handling of these important contexts by the use of Moving Access Points (MAPs). MAPs are capable of autonomously moving and establishing a radio network in short time, with limited centralized management. The radio network provides wireless access to users, is based on ad hoc connectivity (self-adapting mesh network concept), and has some elements acting as gateways to a wide-area infrastructure. The main purpose of this paper is to find the optimal position of the MAPs, i.e., the ones which require minimum movement and telecommunication cost. In order to achieve this goal, an innovative algorithm that combines the well-known simulated annealing algorithm with the characteristic of pheromone of the ant colony optimization is proposed. This is done in order to exploit ant colony optimization concepts in the related problem of the optimization of the MAP-based radio network design. The operation of the algorithm is validated by being applied to three most indicative scenarios, in which it is compared to the pure simulated annealing and a brute-force method, respectively. Our scheme exhibits a 5% improved performance in terms of solution quality in medium and large size problems, a 9% improved speed for the estimation of the suboptimal solution and 15% quicker adaptation to new context, without impacting the computational complexity.     

A tabu search algorithm for routing optimization in mobile ad-hoc networks

In this paper, we propose a routing optimization algorithm to efficiently determine an optimal path from a source to a destination in mobile ad-hoc networks. To determine an optimal path for the nodes is important for transmitting data between nodes in densely deployed networks. In order to efficiently transmit data to its destination, the appropriate routing algorithms must be implemented in mobile ad-hoc networks. The proposed algorithm is designed by using a tabu search mechanism that is a representative meta-heuristic algorithm. The proposed tabu search algorithm carries out two neighborhood generating operations in order to determine an optimal path and minimize algorithm execution time. We compare the proposed tabu search algorithm with other meta-heuristic algorithms, which are the genetic algorithm and the simulated annealing, in terms of the routing cost and algorithm execution time. The comparison results show that the proposed tabu search algorithm outperforms the other algorithms and that it is suitable for adapting the routing optimization problem.     

Meta‐heuristic algorithms for channel scheduling problem in wireless sensor networks

The channel scheduling problem is to decide how to commit channels for transmitting data between nodes in wireless networks. This problem is one of the most important problems in wireless sensor networks. In this problem, we aim to obtain a near‐optimal solution with the minimal energy consumption within a reasonable time. As the number of nodes increases in the network, however, the amount of calculation for finding the solution would be too high. It can be difficult to obtain an optimal solution in a reasonable execution time because this problem is NP‐hard. Therefore, most of the recent studies for such problems seem to focus on heuristic algorithms. In this paper, we propose efficient channel scheduling algorithms to obtain a near‐optimal solution on the basis of three meta‐heuristic algorithms; the genetic algorithm, the Tabu search, and the simulated annealing. In order to make a search more efficient, we propose some neighborhood generating methods for the proposed algorithms. We evaluate the performance of the proposed algorithms through some experiments in terms of energy consumption and algorithm execution time. The experimental results show that the proposed algorithms are efficient for solving the channel scheduling problem in wireless sensor networks. Copyright © 2011 John Wiley & Sons, Ltd.     

Individual wire-length prediction with application to timing-driven placement

In this paper, we address the problem of individual wire-length prediction and demonstrate its usefulness in timing-driven placement. Many researchers have observed that different placement algorithms produce different individual wire lengths. We postulate that to obtain accurate results, individual wire-length prediction should be coupled with the placement flow. We embed the wire-length prediction into the clustering step of our fast placer implementation (FPI) framework . The predicted wire lengths act as constraints for the simulated annealing refinement stage, which guides the placement toward a solution fulfilling them. Experimental results show that our prediction process yields accurate results without loss of quality and incurs only a small cost in placement effort. We successfully apply the wire-length prediction technique to timing-driven placement. Our new slack assignment algorithm with predicted wire lengths (p-SLA) gives on average an 8% improvement in timing performance compared with the conventional modified zero-slack algorithm (m-ZSA).     

A stochastic continuation approach to piecewise constant reconstruction.

We address the problem of reconstructing a piecewise constant 3-D object from a few noisy 2-D line-integral projections. More generally, the theory developed here readily applies to the recovery of an ideal n-D signal (n > or =1) from indirect measurements corrupted by noise. Stabilization of this ill-conditioned inverse problem is achieved with the Potts prior model, which leads to a challenging optimization task. To overcome this difficulty, we introduce a new class of hybrid algorithms that combines simulated annealing with deterministic continuation. We call this class of algorithms stochastic continuation (SC). We first prove that, under mild assumptions, SC inherits the finite-time convergence properties of generalized simulated annealing. Then, we show that SC can be successfully applied to our reconstruction problem. In addition, we look into the concave distortion acceleration method introduced for standard simulated annealing and we derive an explicit formula for choosing the free parameter of the cost function. Numerical experiments using both synthetic data and real radiographic testing data show that SC outperforms standard simulated annealing.     

Adaptive telecommunication system for disabled people

The tremendous growth of telecommunication networks, as well as the huge expansion of mobile phones, is allowing wider communities to access otherwise impossible resources. Information is today available everywhere, and companies are exploiting their ubiquitous presence to increase their value. In this article we will show how our work searches for the human face of technology. Making use of information and telecommunication networks endows people with the necessary set of tools to overcome their problems. In this paper we present a new methodology which is inspired in an open architecture for people with disabilities. This methodology allows them to carry out tasks that are taken for granted by most of us. We begin by describing the communication problems that handicapped people suffer. We then describe the open architecture and technology involved in the solution we are offering. Finally we present our solution for handicapped people with communication problems.     

An adaptive local-search algorithm for the channel-assignmentproblem (CAP)

The channel-assignment problem (CAP) for cellular radio networks is an NP-complete problem. Previous techniques for solving this problem have used graph-coloring algorithms, neural networks, simulated annealing, and pattern-based optimization procedures. We describe an efficient two-phase adaptive local-search algorithm for the channel-assignment problem. This algorithm has been applied to several existing benchmark problems with encouraging results. In many cases it outperforms the existing algorithms in the quality of the solution obtained. When used in conjunction with structured preprocessing, the algorithm can be applied to large networks. It is thus a practical tool for the planning of cellular radio networks     

一种针对频率分配问题的改进ANTS算法

频率分配问题是近年来通信领域研究的热点。针对FAP问题提出了一种结合模拟退火算法的改进ANTS算法。运用模拟退火算法产生次优解,利用次优解分配初始信息素,并利用ANTS算法来寻求最佳方案。在ANTS算法的每个蚂蚁寻找局部最优过程中,为了加快运算速度,对局部寻优过程进行了改进。实验结果表明,在解质量相当的情况下,该算法能够大大地加快收敛速度,特别是针对一些较复杂的分配情况,效果明显。     

Efficient Cache Placement in Multi-Hop Wireless Networks

In this paper, we address the problem of efficient cache placement in multi-hop wireless networks. We consider a network comprising a server with an interface to the wired network, and other nodes requiring access to the information stored at the server. In order to reduce access latency in such a communication environment, an effective strategy is caching the server information at some of the nodes distributed across the network. Caching, however, can imply a considerable overhead cost; for instance, disseminating information incurs additional energy as well as bandwidth burden. Since wireless systems are plagued by scarcity of available energy and bandwidth, we need to design caching strategies that optimally trade-off between overhead cost and access latency. We pose our problem as an integer linear program. We show that this problem is the same as a special case of the connected facility location problem, which is known to be NP-hard. We devise a polynomial time algorithm which provides a suboptimal solution. The proposed algorithm applies to any arbitrary network topology and can be implemented in a distributed and asynchronous manner. In the case of a tree topology, our algorithm gives the optimal solution. In the case of an arbitrary topology, it finds a feasible solution with an objective function value within a factor of 6 of the optimal value. This performance is very close to the best approximate solution known today, which is obtained in a centralized manner. We compare the performance of our algorithm against three candidate cache placement schemes, and show via extensive simulation that our algorithm consistently outperforms these alternative schemes.     

Minimum pilot power for service coverage in WCDMA networks

Pilot power management is an important issue for efficient resource utilization in WCDMA networks. In this paper, we consider the problem of minimizing pilot power subject to a coverage constraint. The constraint can be used to model various levels of coverage requirement, among which full coverage is a special case. The pilot power minimization problem is \({{\cal N}{\cal P}}\)-hard, as it generalizes the set covering problem. Our solution approach for this problem consists of mathematical programming models and methods. We present a linear-integer mathematical formulation for the problem. To solve the problem for large-scale networks, we propose a column generation method embedded into an iterative rounding procedure. We apply the proposed method to a range of test networks originated from realistic network planning scenarios, and compare the results to those obtained by two ad hoc approaches. The numerical experiments show that our algorithm is able to find near-optimal solutions with a reasonable amount of computing effort for large networks. Moreover, optimized pilot power considerably outperforms the ad hoc approaches, demonstrating that efficient pilot power management is an important component of radio resource optimization. As another part of our numerical study, we examine the trade-off between service coverage and pilot power consumption.     

Heuristic and simulated annealing algorithms for solving extended cell assignment problem in wireless ATM networks

In this paper, we investigate the extended cell assignment problem which optimally assigns new adding and splitting cells in Personal Communication Service (PCS) to switches in a wireless Asynchronous Transfer Mode (ATM) network. Given cells in a PCS network and switches on an ATM network (whose locations are fixed and known), we would like to do the assignment in an attempt to minimize a cost criterion. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP‐hard. A heuristic algorithm and a simulated annealing algorithm are proposed to solve this problem. The heuristic algorithm, Extended Assignment Algorithm (EEA), consists of two phases, initial assigning phase and cell exchanging phase. First, in the initial assigning phase, the initial assignments of cells to switches are found. Then, these assignments are improved by performing cell exchanging phase in which two cells are repeatedly exchanged in different switches with great reduction of the total cost. The simulated annealing algorithm, ESA (enhanced simulated annealing), generates constraint‐satisfied configurations, and uses three configuration perturbation schemes to change current configuration to a new one. Experimental results indicate that EAA and ESA algorithms have good performances. Copyright © 2002 John Wiley & Sons, Ltd.     

Network Design Using SMDS and Leased Lines

In this paper we consider designing a high-speed virtual private network using a combination of heterogeneous telecommunication services. In particular, we consider mixing SMDS access lines and point-to-point digital leased lines to construct a virtual private network at minimum cost. We develop a nonlinear combinatorial optimization model and a simulated annealing algorithm to find a high-performance, low-cost network design. We compute lower bounds on cost savings from using mixed services as opposed to pure SMDS based on actual tariffs and realistic traffic.     

Location area planning and cell-to-switch assignment in cellular networks

Location area (LA) planning plays an important role in cellular networks because of the tradeoff caused by paging and registration signalling. The upper boundary for the size of an LA is the service area of a mobile services switching center (MSC). In that extreme case, the cost of paging is at its maximum but no registration is needed. On the other hand, if each cell is an LA, the paging cost is minimal but the cost of registration is the largest. Between these extremes lie one or more partitions of the MSC service area that minimize the total cost of paging and registration. In this paper, we seek to determine the location areas in an optimum fashion. Cell to switch assignments are also determined to achieve the minimization of the network cost. For that purpose, we use the available network information to formulate a realistic optimization problem, and propose an algorithm based on simulated annealing (SA) for its solution. Then, we investigate the quality of the SA-based technique by comparing it to greedy search, random generation methods, and a heuristic algorithm.     

Application of simulated annealing to the biclustering of gene expression data.

In a gene expression data matrix, a bicluster is a submatrix of genes and conditions that exhibits a high correlation of expression activity across both rows and columns. The problem of locating the most significant bicluster has been shown to be NP-complete. Heuristic approaches such as Cheng and Church's greedy node deletion algorithm have been previously employed. It is to be expected that stochastic search techniques such as evolutionary algorithms or simulated annealing might improve upon such greedy techniques. In this paper we show that an approach based on simulated annealing is well suited to this problem, and we present a comparative evaluation of simulated annealing and node deletion on a variety of datasets. We show that simulated annealing discovers more significant biclusters in many cases. Furthermore, we also test the ability of our technique to locate biologically verifiable biclusters within an annotated set of genes.     

A Multiresolution Stochastic Level Set Method for Mumford–Shah Image Segmentation

The Mumford–Shah model is one of the most successful image segmentation models. However, existing algorithms for the model are often very sensitive to the choice of the initial guess. To make use of the model effectively, it is essential to develop an algorithm which can compute a global or near global optimal solution efficiently. While gradient descent based methods are well-known to find a local minimum only, even many stochastic methods do not provide a practical solution to this problem either. In this paper, we consider the computation of a global minimum of the multiphase piecewise constant Mumford–Shah model. We propose a hybrid approach which combines gradient based and stochastic optimization methods to resolve the problem of sensitivity to the initial guess. At the heart of our algorithm is a well-designed basin hopping scheme which uses global updates to escape from local traps in a way that is much more effective than standard stochastic methods. In our experiments, a very high-quality solution is obtained within a few stochastic hops whereas the solutions obtained with simulated annealing are incomparable even after thousands of steps. We also propose a multiresolution approach to reduce the computational cost and enhance the search for a global minimum. Furthermore, we derived a simple but useful theoretical result relating solutions at different spatial resolutions.      

A channel allocation for cellular mobile radio systems using simulated annealing

We consider the channel allocation problem, which is one of the most interesting problems in mobile radio systems. This problem is known to be NP‐complete and a couple of heuristic algorithms have been developed. In this paper, we convert the problem into a simpler form through the concept of pattern, a set of cochannel cells. We suggest another algorithm based on simulated annealing for this simplified problem. The algorithm is applied into different benchmark problems that have appeared in the literature. The presented examples illustrate that our method works very well. Computational results using our formulation and simulated annealing algorithm are reported. This revised version was published online in August 2006 with corrections to the Cover Date.     

Simulated Annealing Based Multi-constrained QoS Routing in Mobile ad hoc Networks

Multi-constrained quality-of-service routing (QoSR) is to find a feasible path that satisfies multiple constraints simultaneously, which is a big challenge for mobile ad hoc networks (MANETs) where the topology may change constantly. It has been proved that such a problem is NP-complete. Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions, most of which suffered either from excessive computational complexities or from low performance were proposed only for wired networks and cannot be used directly in wireless MANETs. In this paper a novel QoS routing algorithm based on Simulated Annealing (SA_RA) is proposed. This algorithm first uses an energy function to translate multiple QoS weights into a single mixed metric and then seeks to find a feasible path by simulated annealing. The paper outlines simulated annealing algorithm and analyzes the problems met when we apply it to QoSR in MANETs. Theoretical analysis and experiment results demonstrate that the proposed method is an effective approximation algorithms showing better performance than the other pertinent algorithm in seeking the (approximate) optimal configuration within a period of polynomial time.     

Preferred Link Based Distributed Adaptive Routing in Wavelength Routed Optical Network

As the WDM technology matures and the demand for bandwidth increases, dynamic provisioning of lightpaths at the WDM layer becomes an important and challenging problem. In this paper, we consider the problem of dynamic routing and wavelength assignment in wavelength-routed optical networks. The conventional approach to this problem is to select a route from a set of candidate routes, which has a common wavelength available on all the links of the route. In this paper, we propose a distributed algorithm which selects a route based on the state of the network (called preferred link approach). In this approach, a route is selected link by link based on a preference value given to each of the links. We propose three different heuristic functions for calculating the preference of the links, depending on the cost and congestion on the links. We evaluate our routing algorithm in terms of call acceptance ratio, cost of the path, hop length, and call setup time. Our experimental results suggest that our algorithm not only out performs the existing methods with respect to average call acceptance ratio, but, also improves the fairness among different hop connections, which is an important result in the case of WDM optical networks.     

On circuit clustering for area/delay tradeoff under capacity andpin constraints

In this paper, we propose an iterative area/delay tradeoff algorithm to solve the circuit clustering problem under the capacity constraint. It first finds an initial delay-considered area-optimized clustering solution by a delay-oriented depth first-search procedure. Then, an iterative procedure consisting of several reclustering techniques is applied to gradually trade the area for the performance. We then show that this algorithm can be easily extended to solve the clustering problem subject to both capacity and pin constraints. Experimental results show that our algorithm can provide a complete set of clustering solutions from the area-optimized one to the delay-optimized one for a given circuit. Furthermore, compared to the existing delay-optimized algorithms, this algorithm achieves almost the same performance but with much less area overhead. Therefore, this algorithm is very useful for solving the timing-driven circuit clustering problem     

Simulated annealing-based algorithms for the studies of thethermoelastic scaling behavior

Simulated annealing is a robust and easy-to-implement algorithm for material simulation. However, it consumes a huge amount of computational time, especially on the studies of percolation networks. To reduce the running time, we parallelize the simulated annealing algorithm in our studies of the thermoelastic scaling behavior of percolation networks. The critical properties of the thermoelastic moduli of percolation networks near the threshold p_c are investigated by constructing a square percolation network. The properties are tested by simulations of a series of two-dimensional (2-D) percolation networks near p_c. The simulations are performed using a novel parallelizing scheme on the simulated annealing algorithm. To further accelerate the computational speed, we also propose a new conjectural method to generate better initial configurations, which speeds up the simulation significantly. Preliminary simulation results show surprisingly that the percolating phenomenon of thermal expansion does exist under certain conditions. The behavior seems to be governed by the elastic properties of a percolation network