On finding minimum cost tree for multi-resource manycast in mesh networks

We investigate the problem of multi-resource manycast in mesh networks. The problem of multi-resource manycast extends the traditional manycast problem or k-Steiner tree problem, which finds a minimum cost tree spanning any k vertices. For the traditional manycast, all the vertices in the set of candidate destinations will be regarded as identical. However, the computing capability of the resource at each vertex may be not equivalent in the realistic networks. In this paper, we consider the problem of multi-resource manycast, in which the computing capability of the resource at a vertex is decomposed into discrete units. That is, each vertex may have multiple units of computing resources. The objective is to find a minimum cost tree spanning any k units of computing resources distributed in the networks. We show that multi-resource manycast is NP-Complete. The ILP formulation and approximation analysis are given for this problem. Simple polynomial-time heuristic algorithms are also proposed for the problem of multi-resource manycast. We investigate various approaches to implement multi-resources manycast in mesh networks, and verify the effectiveness of the approaches through simulation.     

QoS-supporting video streaming system with minimum data service cost over heterogeneous wireless networks

This paper presents a video streaming system that supports quality-of-service by effectively consolidating multiple physical paths in a cost-effective way over heterogeneous wireless networks. In the proposed system, the fountain encoding symbols of compressed video data are transmitted through multiple physical paths concurrently to overcome the limitation of single path transmission and harmonize multiple physical paths with diverse characteristics effectively, and the number of transmitted packets is determined by considering the requested quality-of-service of video streaming and the data service cost. The proposed system is fully implemented in Java and C/C++, and tested over real WLAN and LTE networks. Experimental results are provided to demonstrate the performance improvement of the proposed system.     

On the cost of virtual private networks

A virtual private network (VPN) is a private data network that uses a nonprivate data network to carry traffic between remote sites. An “Intranet VPN” establishes network layer connectivity between remote Intranet sites by creating an IP overlay network over the nonprivate network, using various tunneling mechanisms. There are two approaches for establishing such tunnels: a “CPE-based approach” and a “network-based approach.” In the first approach, tunnels are established only between the CPE devices, whereas in the second approach tunnels are also established between the routers of the core nonprivate network. In this paper we address the problem of determining a CPE-based and a network-based layout of VPN tunnels while taking into account two factors: the cost of the links over which the VPN tunnels are established and the cost of the core routers that serve as end points for the VPN. We define related graph algorithm problems, analyze their complexity, and present heuristics for solving these problems efficiently     

On the cost of fairness in ring networks

The impact of fairness on the throughput of ring networks with spatial reuse is investigated. A model for a slotted ring with spatial reuse that employs a simple fairness mechanism is presented. An exact expression for the expected time taken to evacuate this ring when each node initially contains one packet is derived. The expected evacuation time is used to obtain an exact expression for the throughput of the ring. It is shown that as the number of nodes on the ring increases, the penalty for fairness in terms of throughput becomes negligible     

Cross-layer optimization with cooperative communication for minimum power cost in packet error rate constrained wireless sensor networks

This paper addresses the problem of joint design of routing, medium access control (MAC), and physical layer protocols with cooperative communication to achieve minimum power cost in packet error rate (PER) constrained wireless sensor networks (WSNs). The problem is solved in two steps. First, we calculate the minimum power cost with a specified PER objective between any two nodes, assuming either cooperative (with a single relay node) or direct communication between the two nodes. It is shown that the minimum per-hop power cost is found in 2M and log₂ M steps for cooperative and direct communication, respectively, where M is the number of power levels. Second, we formulate the cross-layer design problem as a linear optimization problem to minimize the power cost of the whole network, using the minimum per-hop power cost determined in the first step as input and assuming time division multiple access (TDMA) at the MAC layer. Numerical results show that, at a desired end-to-end PER objective, cross-layer optimization with cooperative communication achieves up to 70% of power savings compared to that without cooperative communication.     

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.     

On the minimum hop count and connectivity in one-dimensional ad hoc wireless networks

This paper investigates connectivity in one-dimensional ad hoc networks by means of the distribution of the minimum hop count between source and destination nodes. We derive the exact probability distribution of the minimum hop count from the location density of relay nodes in the multihop path selected with the Most Forward within Radius (MFR) scheme. The probability that the source and destination nodes are connected (provided by Ghasemi and Nader-Esfahani [IEEE Commun. Lett. 10(4):251–253, 2006]) can be obtained by summing the probability masses for each possible value of the minimum hop count, which provides new insights to the connectivity probability. Numerical results show the effect of the number of nodes and the transmission range on the minimum hop count.     

On formulation of a reliable cost allocation strategy in centralized computer networks

Centralized networks arise in the context of communications between terminals and a Central processing unit or in the context of the design of local distribution network. The basic problem of cost allocation in a network is: “How much should each user be charged for his portion of the services supplied”? The minimum cost required to connect all the consumers to the central supplier (using arcs of the network) is the length of a shortest spanning tree. The question then is how to divide the total cost of this shortest spanning tree to the consumers. In this paper, we present a relative study of a number of possible cost-allocation methods. Based on the suggested criteria formulated as a tradeoff between the satisfaction of user and company holders, a comparative evaluation is tabulated, which can be used as a qualitative guideline while forming a “reliable” as well as near optimal cost-allocation strategy depending upon the locally prevailing conditions also.     

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.     

时分-波分复用网络中的最短帧长算法

无源星形时分-波分复用(TWDM,Time-Wavelength Division Multiplexing)网络是一种前景广阔的大容量高速通信网络,在任意业务量分布及任意可调光器件的调谐时间的条件下进行最短帧长设计是TWDM网络中的核心问题之一。本文就这一问题提出了一种新型的算法MTC,与已有的算法相比,MTC可以获得更优良的性能,是一种高效的TWDM访问控制协议。     

Interference minimum network topologies for ad hoc networks

This paper investigates the topology control problem with the goal of minimizing mutual interferences in wireless ad hoc networks. It is known that interference is considered as a relationship between link and node in previous works. In this paper, we attempt to capture the physical situation of space‐division multiplex more realistically by defining interference as a relationship between any two bidirectional links. We formulate the pair‐wise interference condition between any two bidirectional links, and demonstrate that the interference condition is equivalent by employing the equal‐power allocation strategy and by employing the minimum‐power allocation strategy. Then we further study the typical interference relationship between a link and its surrounding links. To characterize the extent of the interference between a link and its surrounding links, a new metric, the interference coefficient, is given, and its property is explored in detail by means of analysis and simulation. Based on the insight obtained, a centralized algorithm, BIMA, and a distributed algorithm, LIMA, are proposed to control the network interference. Our simulation indicates that BIMA can minimize the network interference while conserving energy and maintaining good spanner property, and LIMA has relatively good interference performance while keeping low node degree, compared with some well‐known algorithms. Besides, both BIMA and LIMA show good robustness to additive noises in terms of interference performance. Copyright © 2010 John Wiley & Sons, Ltd.     

A distributed minimum variance estimator for sensor networks

A distributed estimation algorithm for sensor networks is proposed. A noisy time-varying signal is jointly tracked by a network of sensor nodes, in which each node computes its estimate as a weighted sum of its own and its neighbors' measurements and estimates. The weights are adaptively updated to minimize the variance of the estimation error. Both estimation and the parameter optimization is distributed; no central coordination of the nodes is required. An upper bound of the error variance in each node is derived. This bound decreases with the number of neighboring nodes. The estimation properties of the algorithm are illustrated via computer simulations, which are intended to compare our estimator performance with distributed schemes that were proposed previously in the literature. The results of the paper allow to trading-off communication constraints, computing efforts and estimation quality for a class of distributed filtering problems.     

基于最小代价路径的交换机迁移方法研究

针对如何保护控制器,尤其是骨干控制器免受安全威胁与攻击,提高SDN控制平面的安全性,提出一种基于最小代价路径的交换机迁移算法。在迁移模型中加入负载预测模块,预测模块执行控制器负载预测算法,得到负载预测矩阵,然后根据负载预测矩阵确定迁出、目标控制器集合。利用改进的迪杰斯特拉算法确定最小代价路径,根据控制器的负载状态和待迁移交换机的流量优先级,在最小代价路径中确定最优迁移交换机集合,同时针对迁移过程中可能产生的孤立节点问题给出了解决方案。实验结果表明,所提算法确定的迁移触发时机、迁出控制器和目标控制器更加合理,减少了迁移次数和代价,增强了控制器的安全性,提高了控制器性能。     

A minimum cost heterogeneous sensor network with a lifetime constraint

We consider a heterogeneous sensor network in which nodes are to be deployed over a unit area for the purpose of surveillance. An aircraft visits the area periodically and gathers data about the activity in the area from the sensor nodes. There are two types of nodes that are distributed over the area using two-dimensional homogeneous Poisson point processes; type 0 nodes with intensity (average number per unit area) /spl lambda//sub 0/ and battery energy E/sub 0/; and type 1 nodes with intensity /spl lambda//sub 1/ and battery energy E/sub 1/. Type 0 nodes do the sensing while type 1 nodes act as the cluster heads besides doing the sensing. Nodes use multihopping to communicate with their closest cluster heads. We determine them optimum node intensities (/spl lambda//sub 0/, /spl lambda//sub 1/) and node energies (E/sub 0/, E/sub 1/) that guarantee a lifetime of at least T units, while ensuring connectivity and coverage of the surveillance area with a high probability. We minimize the overall cost of the network under these constraints. Lifetime is defined as the number of successful data gathering trips (or cycles) that are possible until connectivity and/or coverage are lost. Conditions for a sharp cutoff are also taken into account, i.e., we ensure that almost all the nodes run out of energy at about the same time so that there is very little energy waste due to residual energy. We compare the results for random deployment with those of a grid deployment in which nodes are placed deterministically along grid points. We observe that in both cases /spl lambda//sub 1/ scales approximately as /spl radic/(/spl lambda//sub 0/). Our results can be directly extended to take into account unreliable nodes.     

Minimum cost dimensioning of ring optical networks

We consider the problem of traffic grooming of low-rate traffic circuits in WDM rings where circuits are associated with a set of heterogeneous granularities. While networks are no longer limited by transmission bandwidth, the key issue in WDM network design has evolved towards the processing capabilities of electronic switches, routers and multiplexers. Therefore, we focus here on traffic grooming with minimum interconnecting equipment cost. We first formulate the problem as an integer linear programming (ILP) or a mixed integer linear programming (MILP) problem depending on the design specifications: UPSR vs BLSR, fixed vs variable wavelength capacities, non-bifurcated vs bifurcated flows, wavelength continuity vs possible signal regeneration on a different wavelength. Considering the case study of the second SONET ring generation with MSPP like interconnection equipment, we define the cost by a function of the number of transport blades, taking into account that the number of MSPP transport blades makes up a significant portion of the overall network design cost. Using the CPLEX linear programming package, we next compare the optimal solutions of the ILP or MILP programs for different design assumptions, including the classical ring network design scheme with a single hub where the lightpaths directly connect the hub to all other nodes.     

The cost of quality in Internet-style networks

In broad terms, the quality of service (QoS) of a wide-area network is a measure: of how well it does its job-how quickly and reliably it transfers various kinds of data, including digitized voice and video traffic, from source to destination. With the advent of packet switching and the proliferation of many kinds of communications traffic (time-sensitive financial transactions, still images, large data files, voice, video, and so on), there are more than one set of criteria to satisfy. The the data rate needed for satisfactory voice communication may take an intolerable time to transfer high-resolution images. Conversely, the degree of network latency acceptable in transferring some files may not be adequate for real-time voice. So QoS has become a hot topic, and the contracts that specify it, called service level agreements (SLAs), are becoming more and more common, at least between service providers and their largest customers. As incumbent providers of telecommunications service are increasingly being challenged by competitive carriers, QoS has become a convenient marketing tool for both. The ability truly to deliver quality of service will separate the winner from the losers in the packet-switched future. The paper defines QoS, its priorities, and improvement     

基于二阶差分的加权最小费用流相位展开算法

相位展开是光学干涉相位测量技术中的重要步骤,由于噪声、欠采样等因素的影响,精确的相位展开变得非常困难。将相位的二阶差分和最小费用流算法结合,提出一种以相位的二阶差分作为最小费用流权重的相位展开算法。模拟计算表明,该算法既可有效地避免枝切法由于连接的枝切形成闭合区域导致局部相位不能展开的问题,又可减小最小二乘法近似逼近带来的较大误差,相对于未设置权值的最小费用流算法,提高了其相位展开的精度。对三维形貌测量中的实验数据相位展开结果,证明了该算法的有效性。     

Minimal cost coverage planning for single frequency networks

OFDM based single frequency networks (SFNs) have been standardized for terrestrial broadcasting systems, for digital audio broadcasting (DAB) as well as for digital video broadcasting (DVB). Due to the multipath tolerance of the OFDM scheme, the receiver is able to combine signals coming from several transmitters, despite of the varying propagation delays, i.e., heavy artificial multipath propagation. In order to take full advantage of the diversity gain provided by the SFN architecture, proper network design is required. We focus on the cost efficient design of an SFN providing broadcasting services over a predefined service area with requirements both on the received signal quality and on the allowable interference level experienced by existing services in the same spectrum. We formulate the problem as a discrete optimization problem, where the network design parameters such as power, antenna heights and transmitter locations are the decision variables. The general stochastic optimisation algorithm simulated annealing has been adapted for solving the above problem. The novelty of our method is that cost factors and interference constraints are embedded in the optimisation procedure. Through numerical examples we demonstrate that significant reduction in network cost can be achieved by our approach     

Simultaneous area and delay minimum K-LUT mapping for K-exact networks

We address the technology mapping problem for lookup table FPGAs. The area minimization problem, for mapping K-bounded networks, consisting of nodes with at most K inputs, using K-input lookup tables, is known to be NP-complete for K 5. The complexity was unknown for K = 2, 3, and 4. The corresponding delay minimization problem (under the constant delay model) was solved in polynomial time by the flow-map algorithm, for arbitrary values of K. We study the class of K-bounded networks, where all nodes have exactly K inputs. We call such networks K-exact. We give a characterization of mapping solutions for such networks. This leads to a polynomial time algorithm for computing the simultaneous area and delay minimum mapping for such networks using K-input lookup tables. We also show that the flow-map algorithm computes the same mapping solution as our algorithm. We then show that for K = 2 the mapping solution for a 2-bounded network, minimizing the area and delay simultaneously, can be easily obtained from that of a 2-exact network derived from it by eliminating single input nodes. Thus the area minimization problem for 2-input lookup tables can be solved in polynomial time, resolving an open problem.