Allocation of Splitting Nodes in All-Optical Wavelength-Routed Networks

In this paper, we introduce the splitter placement problem in wavelength-routed networks (SP-WRN). Given a network topology, a set of multicast sessions, and a fixed number of multicast-capable cross-connects, the SP-WRN problem entails the placement of the multicast-capable cross-connects so that the blocking probability is minimized. The SP-WRN problem is NP-complete as it includes as a subproblem the routing and wavelength assignment problem which is NP-complete. To gain a deeper insight into the computational complexity of the SP-WRN problem, we define a graph-theoretic version of the splitter placement problem (SPG), and show that even SPG is NP-complete. We develop three heuristics for the SP-WRN problem with different degrees of trade-off between computation time and quality of solution. The first heuristic uses the CPLEX general solver to solve an integer-linear program (ILP) of the problem. The second heuristic is based on a greedy approach and is called most-saturated node first (MSNF). The third heuristic employs simulated annealing (SA) with route-coordination. Through numerical examples on a wide variety of network topologies we demonstrate that: (1) no more than 50% of the cross-connects need to be multicast-capable, (2) the proposed SA heuristic provides fast near-optimal solutions, and (3) it is not practical to use general solvers such as CPLEX for solving the SP-WRN problem.     

Finding Multiple Coherent Biclusters in Microarray Data Using Variable String Length Multiobjective Genetic Algorithm

Microarray technology enables the simultaneous monitoring of the expression pattern of a huge number of genes across different experimental conditions. Biclustering in microarray data is an important technique that discovers a group of genes that are coregulated in a subset of conditions. Biclustering algorithms require to identify coherent and nontrivial biclusters, i.e., the biclusters should have low mean squared residue and high row variance. A multiobjective genetic biclustering technique is proposed here that optimizes these objectives simultaneously. A novel encoding scheme that uses variable chromosome length is developed. Moreover, a new quantitative measure to evaluate the goodness of the biclusters is proposed. The performance of the proposed algorithm has been evaluated on both simulated and real-life gene expression datasets, and compared with some other well-known biclustering techniques.      

Combining strategies for the optimization of resource allocation in a wireless multiuser OFDM system

Wireless transmission systems are constrained by several parameters such as the available spectrum bandwidth, the mobile battery autonomy, the channel impairments, the transmission power, etc. In this paper, we investigate new strategies that aim at improving the allocation of resources in cognitive radio systems based on Orthogonal Frequency Division Multiplexing. We propose several techniques for the dynamic assignment of available subcarriers in such a way to maximize the mobile autonomy in uplink communications and minimize the required amount of bandwidth in downlink. In both transmission links, the system must guarantee a certain transmission data rate to each user. An iterative greedy approach, which assigns the users that have the weakest battery level or the smallest transmission rate the most favorable subcarriers, is introduced in order to maximize the overall system throughput. We show how an optimal solution for the combinatorial optimization problem can be determined by complex algorithms inspired by the field of statistical mechanics. Fortunately, our results show that for moderate values of the required data rates and the number of users, our greedy approach performs almost as well as the simulated annealing technique but with a much more affordable complexity.     

一种结合模拟退火和贪心策略的社团识别算法

为了提高复杂网络社团识别的精度和速度,文中结合模拟退火和贪心策略识别社团结构的优势,提出一种新的社团识别算法。该算法利用贪心策略引导模拟退火搜索最优解过程中单个结点的无规则盲目移动,消除了大量无效移动,在搜索到全局最优解的情况下,将搜索时间大幅缩减。实验表明,SAGA具有强大的搜索能力和较快的模拟退火执行速度,可获得较高的模块度,达到较为准确的社团分割,且具有一定的应用价值。     

无线传感器网络路由协议的设计与实现

针对传统路由协议端到端时延长、丢包率过高的现实问题,提出了一种基于贪婪转发的能量感知多路径路由协议(Greedy Forward Energy-aware Multipath Routing Protocol,GFEMRP)。GFEMRP从传感器起始结点出发,如果遇到网络黑洞则选择周边转发方式,否则将选择吞吐量大、且更接近于目的结点的结点作为下一跳结点。利用了OMNET++5.0和INET框架对包括无线自组网按需平面距离向量路由协议(Ad hoc on-demand distance vector routing protocol,AODV),动态按需无线自组织网络(Dynamic MANET On-demand,DYMO),贪婪周边无状态路由无线网络(Greedy Perimeter Stateless Routing for Wireless Networks,GPSR)和GFEMRP协议在内的四种路由协议进行了仿真和比较,实验结果表明GFEMRP协议具有良好的端到端时延、丢包率等性能。     

Sum capacity of the reverse link for multi-cell multi-user cellular systems

This letter studies the information-theoretic sum capacity of the reverse link for multi-cell, multi-user cellular systems subjected to a peak power constraint. It is proven that, for the optimal scheduling, there will be at most one user transmitting at part of the peak power within each cell. Therefore, we approximate the optimization scheduling problem to a combination optimization problem which can be solved by standard simulated annealing algorithm. Further, we propose a low complexity cell greedy scheduling algorithm which can achieve almost the same performance as simulated annealing algorithm.     

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.     

3-D Floorplanning: Simulated Annealing and Greedy Placement Methods for Reconfigurable Computing Systems

The advances in the programmable hardware has lead to new architectures where the hardware can be dynamically adapted to the application to gain better performance. There are still many challenging problems to be solved before any practical general-purpose reconfigurable system is built. One fundamental problem is the placement of the modules on the reconfigurable functional unit (RFU). In reconfigurable systems, we are interested both in online placement, where arrival time of tasks is determined at runtime and is not known a priori, and offline in which the schedule is known at compile time. In the case of offline placement, we are willing to spend more time during compile time to find a compact floorplan for the RFU modules and utilize the RFU area more efficiently. In this paper we present offline placement algorithms based on simulated annealing and greedy methods and show the superiority of their placements over the ones generated by an online algorithm.     

Modeling adaptive node capture attacks in multi-hop wireless networks

We investigate the problem of modeling node capture attacks in heterogeneous wireless ad hoc and mesh networks. Classical adversarial models such as the Dolev–Yao model are known to be unsuitable for describing node capture attacks. By defining the amortized initialization overhead cost as well as the cost of capturing a node, we show that finding the node capture attack yielding the minimum cost can be formulated as an integer-programming minimization problem. Hence, there is no polynomial solution to find the minimum cost node capture attack. We show that depending on the adversary’s knowledge of the constraint matrix in the integer-programming problem, different greedy heuristics can be developed for node capture attacks. We also show under what conditions privacy-preserving key establishment protocols can help to prevent minimum cost node capture attacks. Individual node storage randomization is investigated as a technique to mitigate the effect of attacks which are not prevented by the use of privacy-preserving protocols. It is shown that probabilistic heuristic attacks can be performed effectively even under storage randomization.     

Energy efficient broadcast routing in static ad hoc wireless networks

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard and propose three heuristic algorithms, namely, shortest path tree heuristic, greedy heuristic, and node weighted Steiner tree-based heuristic, which are centralized algorithms. The approximation ratio of the node weighted Steiner tree-based heuristic is proven to be (1 + 2 ln(n - 1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.     

Telecommunication access network design with reliability constraints

In this paper, we study the problem of the design of telecommunication access networks with reliability constraints. These networks form an important part of the telecommunications infrastructure of large organizations, such as banks. Using data patterned after an actual bank network in the U.S., we formulate an optimization model for this problem which specifically takes into account the various cost, and discount structures offered by telecommunication carriers. We then develop dedicated solution procedures for obtaining solutions. Starting from a cluster solution, we then use perturbation techniques which we developed specifically for this problem within an overall simulated annealing solution algorithm. We show how to make the solution procedure more efficient by implicitly determining the values for many variables. We then report the results of our computational testing for a variety of problems. We compare our solution to a lower bound obtained using a linear programming relaxation. We show that substantial cost savings can be realized with our model, and solution procedure. Finally, we discuss which types of annealing steps in the simulated annealing algorithm are important.     

水下无线传感器网络目标跟踪低复杂度节点行径策略

针对水下无线传感器网络节点选择“组合爆炸冶的问题,研究了低计算复杂度节点选择问题。首先,在量化量测的条件下推导了后验克拉美罗下界(PCRLB)与节点位置的关系,为节点选择提供了准则;然后,将GBFOS 算法、贪心算法和随机算法与推导的PCRLB 相结合,设计了低计算复杂度的节点选择策略。实验结果表明,GBFOS 算法和贪心算法可以在保持跟踪性能不退化的情况下,大幅度降低计算复杂度,非常适合解决密集水下网络节点选择问题。此外,还将GBFOS 算法应用到非理想信道条件下节点选择问题,实验结果显示考虑非理想信道的影响可以大幅提高跟踪性能。     

Simulating Greedy Propagation of P2P Worms

Greedy propagation policy for un-structured P2P worms employs the neighboring node list of each node in peer-to-peer(P2P) network to speed up the propagation of P2P worms.After describing the technique background of P2P worms,the algorithm of greedy propagation is addressed.Simulating design for this novel propagation policy is also described.Then,the effects of the greedy propagation policy on spreading speed,convergent convergence speed,and attacking traffic in static P2P worms are simulated and discussed.The primary experimental results show that the greedy propagation is harmful and can bring severe damages to P2P network.     

Application of Rollout Strategy to Test Points Selection for Integer-Coded Fault Wise Table

Test points selection for integer-coded fault wise table is a discrete optimization problem. The global minimum set of test points can only be guaranteed by an exhaustive search which is eompurationally expensive. In this paper, this problem is formulated as a heuristic depth-first graph search problem at first. The graph node expanding method and rules are given. Then, rollout strategies are applied, which can be combined with the heuristic graph search algorithms, in a computationally more efficient manner than the optimal strategies, to obtain solutions superior to those using the greedy heuristic algorithms. The proposed rollout-based test points selection algorithm is illustrated and tested using an analog circuit and a set of simulated integer-coded fault wise tables. Computa- tional results are shown, which suggest that the rollout strategy policies are significantly better than other strategies.     

Base Station Location -Aware Optimization Model of the Lifetime of Wireless Sensor Networks

Recently, wireless sensor networks (WSNs) have been progressively applied in various fields and areas. However, its limited energy resources is indisputably one of the weakest point that strongly affects the network’s lifetime. A WSN consists of a sensor node set and a base station. The initial energy of each sensor node will be depleted continuously during data transmission to the base station either directly or through intermediate nodes, depending on the distance between sending and receiving nodes. This paper consider determining an optimal base station location such that the energy consumption is kept lowest, maximizing the network’s lifetime and propose a nonlinear programming model for this optimizing problem. Our proposed method for solving this problem is to combine methods mentioned in [1] respectively named the centroid, the smallest total distances, the smallest total squared distances and two greedy methods. Then an improved greedy method using a LP tool provided in Gusek library is presented. Finally, all of the above methods are compared with the optimized solution over 30 randomly created data sets. The experimental results show that a relevant location for the base station is essential.     

Social optimum in social groups with give‐and‐take criterion

We consider a ‘Social Group’ of networked nodes, seeking a ‘universe’ of segments. Each node has a subset of the universe and access to an expensive resource for downloading data. Nodes can also acquire the universe by exchanging copies of segments among themselves, at low cost, using inter‐node links. While exchanges over inter‐node links ensure minimum cost, some nodes in the group try to exploit the system. We term such nodes as ‘non‐reciprocating nodes’ and prohibit such behavior by proposing the ‘give‐and‐take’ criterion, where exchange is allowed if each node has segments unavailable with the other. Under this criterion, we consider the problem of maximizing the number of nodes with the universe at the end of local exchanges. First, we present a randomized algorithm that is shown to be optimal in the asymptotic regime. Then, we present greedy links algorithm, which performs well for most of the scenarios and yields an optimal result when the number of nodes is four. The polygon algorithm is proposed, which yields an optimal result when each of the nodes has a unique segment. After presenting some intuitive algorithms (e.g., greedy incremental algorithm and rarest first algorithm), we compare the performances of all proposed algorithms with the optimal. Copyright © 2015 John Wiley & Sons, Ltd.     

模拟退火算法在无线传感器网络定位中的应用

近年来,随着对无线传感器网络研究的不断深入,节点定位问题受到了国内外研究者的极大关注。在深入研究无线传感器网络节点定位和模拟退火算法的基础上,提出了一种新颖的无线传感器网络节点定位算法,着重介绍了算法的基本原理和实现方法。仿真实验结果表明,该算法取得了良好的定位效果。该算法设计简单,计算量小,比较适合于无线传感器网络的节点定位。     

MANET中一种具有能量意识的无信标地理路由算法

 地理路由具有有效的传输性能和良好的可扩展能力,是当前移动Ad Hoc网络路由算法中的一个研究热点. 在许多实际场合下,网络中的节点能量有限并且难以补充,所以合理调整节点之间的能量消耗成为提高网络寿命的一种重要手段. 本文针对贪婪转发和空洞解决方案中存在的节点能量消耗不平衡的问题,提出了一种具有能量意识的无信标地理路由算法EBGR (Energy-Aware and Beaconless Geographic Routing). 该算法包括两个模式：贪婪竞争策略和空洞解决策略. 在贪婪竞争策略中,源节点或中继节点（即上游节点）广播数据包,位于数据包转发域内具有最小动态转发延迟的节点（即下游节点）转发数据包,其余候选节点侦听到该广播包后,自动放弃转发该数据包. 当遇到节点空洞时,将角度和能量信息同时加入到转发节点的动态延迟计算中,从而在数据包转发过程中有效地避绕空洞和平衡节点间的能量消耗. 仿真结果表明,与已有的BLR和GEAR等典型地理路由算法相比,平均投递率提高2%到4%;平均网络寿命提高了10%到20%.     

Channel assignment in cellular radio networks

The authors investigate algorithms based on simulated annealing to solve the channel assignment problem for cellular radio networks. The blocking probability of a network is chosen as the optimization criterion. In order to check the quality of the solutions obtained by simulated annealing, they examine some special types of networks which allow an effective calculation of optimal solutions by tailored algorithms. Their investigations show that simulated annealing is a very powerful tool for solving channel assignment problems     

一种基于混合智能算法的协作中继选择新方法

针对多用户多中继场景下协作通信系统的中继选择问题,提出了一种基于混合智能算法的协作中继选择新方法。不同于现有的为每个源节点分配一个中继节点的中继选择方法,新方法建立了为每个源节点分配一个或多个中继节点的优化模型,以最大化多用户多中继协作系统的最小接收信噪比为优化目标,采用结合了模拟退火与遗传算法的混合智能算法来搜寻中继选择问题的最优解。仿真结果表明,所提方法可显著提高目的端的接收信噪比,且算法具有较强的全局搜索和快速寻优能力。