检索结果-内蒙古大学图书馆

Minimum-energy multicast in wireless ad hoc networks with adaptive antennas: MILP formulations and heuristic algorithms

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2006年第4期5卷 333-346页

作者： Guo, S Yang, O Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada

In this paper, we consider wireless ad hoc networks that use adaptive antennas and have limited energy resources. To explore the advantages of power saving offered by the use of adaptive antennas, we consider the case of source initiated multicast traffic. We present a constraint formulation for the MEM (Minimum-Energy Multicast) problem in terms of MILP (mixed integer linear programming) for wireless ad hoc networks. An optimal solution to the MEM problem using our MILP model can always be obtained in a timely manner for moderately sized networks. In addition to the theoretical effort, we also present two polynomial-time heuristic algorithms called RB-MIDP and D-MIDP to handle larger networks for which the MILP model may not be computationally efficient. The experimental results show that our algorithms compare well with other proposals discussed in this paper.

关键词： wireless ad hoc networks minimum-energy routing multicast algorithm mixed integer linear programming adaptive antenna tree construction

来源：评论

学校读者我要写书评

暂无评论

A new approach based on the surrogating method in the project time compression problems

引用

ANNALS OF OPERATIONS RESEARCH 2006年第1期143卷 237-250页

作者： Bidhandi, HM Islamic Azad Univ Tehran S Branch Dept Ind Engn Tehran Iran

This paper develops a mathematical model for project time compression problems in CPM/PERT type networks. It is noted this formulation of the problem will be an adequate approximation for solving the time compression problem with any continuous and non-increasing time-cost curve. The kind of this model is mixed integer linear Program (MILP) with zero-one variables, and the Benders' decomposition procedure for analyzing this model has been developed. Then this paper proposes a new approach based on the surrogating method for solving these problems. In addition, the required computer programs have been prepared by the author to execute the algorithm. An illustrative example solved by the new algorithm, and two methods are compared by several numerical examples. Computational experience with these data shows the superiority of the new approach.

关键词： networks mixed integer linear programming Benders' decomposition surrogating method

来源：评论

学校读者我要写书评

暂无评论

Cross decomposition of the degree-constrained minimum spanning tree problem

Cross decomposition of the degree-constrained minimum spanni...

引用

10th World Multi-Conference on Systemics, Cybernetics and Informatics/12th International Conference on Information Systems Analysis and Synthesis

作者： Sohn, Han-Suk Bricker, Dennis L. New Mexico State Univ Dept Ind Engn Las Cruces NM 88003 USA Univ Iowa Dept Mech & Ind Engn Iowa City IA USA

ISBN: (纸本)9789806560710

As computer communication networks become a prevalent part in our daily life, the importance of efficient design of those networks becomes more evident. One of the critical issues in the network design process is the topological design problem involved in establishing a centralized data communication network with best performance and low costs. It can be recognized as a degree-constrained minimum spanning tree and it has been shown to be NP-hard. The degree-constrained minimum spanning tree problem commonly appears as a subproblem in the design of centralized data communication networks, and so the development of effective algorithms has received much attention in the research literature. To achieve effectiveness in solving degree-constrained minimum spanning tree, a solution algorithm based on cross-decomposition is proposed in this paper. The computational results are analyzed to demonstrate the effectiveness of the proposed algorithm. It shows a great promise in the design of centralized data communication networks.

关键词： cross-decomposition degree-restriction minimum spanning tree network design mixed integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Building optimal generation bids of a hydro chain in the day-ahead electricity market under price uncertainty

Building optimal generation bids of a hydro chain in the day...

引用

9th International Conference on Probabilistic Methods Applied to Power Systems

作者： Garcia-Gonzalez, Javier Parrilla, Ernesto Mateo, Alicia Moraga, Rocio U Pontificia Comillas Inst Invest Tecnol Madrid Spain Gamesa Energia Wind Market Madrid 28015 Spain

ISBN: (纸本)9789171785855

This paper presents a model to build the optimal generation bids of a set of connected hydro plants in a deregulated system organized as a day-ahead market The generation company is assumed to be price-taker, and therefore, market prices are considered exogenous variables. The main problem of the utility is to find the optimal hourly energy blocks that should submit to the market for each one of its units in order to: 1) maximize the expected profit taking into account some risk aversion criterion, 2) ensure that, after the auction, the obtained cleared schedule is technically feasible. Price uncertainty is introduced via scenarios generated by an Input/Output Hidden Markov Model (IOHMM). In order to be protected against low prices scenarios, a minimum conditional value-at-risk (CVaR) constraint has been included. The model takes into account a very detailed representation of the generating units, and it is formulated as a MILP optimization problem. Its application to a real-size example case is presented and discussed in this paper with satisfactory results.

关键词： hydroelectric power generation mixed integer linear programming short-term hydro scheduling day-ahead energy markets profit maximization risk-aversion CVaR

来源：评论

学校读者我要写书评

暂无评论

Nested partitions method for the local pickup and delivery problem

Nested partitions method for the local pickup and delivery p...

引用

IEEE International Conference on Automation Science and Engineering

作者： Pi, Liang Pan, Yunpeng Shi, Leyuan Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA TomoTherapy Inc Madison WI 53717 USA

ISBN: (纸本)9781424403103

We consider a problem in which a set of loads are to be moved by vehicles in a local service area in an optimal manner so as to maximize the overall profit over a given planning horizon. The problem is a general transportation problem with nonhomogeneous resources, and mixed integer linear programming (MILP) formulations are adopted, which can then be solved using off-the-shelf MILP solvers. Furthermore, we embark on a new approach based on a specialization of the Nested Partitions (NP) method-a meta-heuristic for combinatorial optimization problems. We also propose a number of NP-oriented techniques: (i) linear programming (LP) solution-based biased sampling, which turns to LP solution information for guidance toward good solutions, (ii) sampling-based (or LP solution-based) partitioning that uses sampling results (or the LP solution information) for purposes of deriving effective partitioning schemes, flexible backtracking, etc. These techniques, when used in conjunction with NP, can substantially enhance its efficacy. Our computational results show that on problems of realistic scale, our adapted NP approach overwhelmingly outperforms the standard approach of applying a commercial solver (ILOG CPLEX 9.1 in our experiments) to MILP formulations in terms of both computation time and solution quality.

关键词： nested partitions mixed integer linear programming pickup and delivery nonhomogeneous resources time windows

来源：评论

学校读者我要写书评

暂无评论

Two-phase fine-grain sleep transistor insertion technique in leakage critical circuits 06

Two-phase fine-grain sleep transistor insertion technique in...

引用

International Symposium on Low Power Electronics and Design

作者： Wang, Yu Liu, Yongpan Luo, Rong Yang, Huazhong Wang, Hui Tsinghua Univ EE Dept Beijing 100084 Peoples R China

ISBN: (纸本)1595934626

Multi-threshold CMOS is a valuable leakage reduction method in circuit standby mode. Reducing leakage current through fine-grain sleep transistor insertion (FGSTI) makes it easier to guarantee circuit functionality and improves circuit noise margins. In this paper, we first indicate the negligible dependence of ST size on the amount of leakage saving which makes the two-phase FGSTI reasonable based on our leakage current and delay models. Then we introduce a novel two-phase FGSTI technique: a) ST placement and b) ST sizing, which are formally modeled as two linear programming (LP) models respectively. Our experimental results show that the two-phase FGSTI technique can achieve 78.91%, 92.55%, 97.97% leakage saving when the circuit slowdown is 0%, 3%, 5% respectively. Comparing to the simultaneous ST placement and sizing method using mix integer linear programming (MLP) [1], our technique leads to on average 2% more leakage current reduction while at least 10X runtime saving since fewer variables and constraints with less approximation are used in the LP models. When the circuit slowdown is large enough to perform conventional fixed slowdown method, our technique can still achieve 75.48% ST area saving. Moreover, we show that when the circuit slowdown is 0%, it should be carefully considered to use FGSTI technique due to a large amount of leakage feedback gates.

关键词： leakage current reduction two-phase fine-grain sleep transistor insertion mixed integer linear programming

来源：评论

学校读者我要写书评

暂无评论

linear programming and language processing for human/unmanned-aerial-vehicle team missions

引用

JOURNAL OF GUIDANCE CONTROL AND DYNAMICS 2006年第2期29卷 303-313页

作者： Schouwenaars, T Valenti, M Feron, E How, J Roche, E MIT Dept Aeronaut & Astronaut Informat & Decis Syst Lab Cambridge MA 02139 USA Telegram Corp Cambridge MA 02138 USA

This paper presents a manned-vehicle/unmanned-aerial-vehicle (UAV) mission system that enables an operator in a manned aircraft to issue mission level commands to an autonomous aircraft in real time. A natural language interface allows the manned and unmanned vehicle to communicate in languages understood by both agents. A task scheduler transforms the commands into a dynamic mission plan consisting of task waypoints. These are then given to a mixed-integer linear programming (MILP)-based trajectory optimizer, which safely guides the vehicle through a partially known environment in real time. The MILP trajectory planning formulation and its implementation are discussed in detail. Integrated simulation and June 2004 flight-test results that used an F-15 and an autonomous T-33 equipped with Boeing's unmanned combat air vehicle (UCAV) avionics package are. presented. These activities were part of the Capstone Demonstration of the Defense Advanced Research Projects Agency-sponsored Software Enabled Control effort. The flight tests mark the first time that an onboard MILP-based guidance system was used to control a UAV They also mark the first time that a natural language interface was used by a manned vehicle to task a UAV in real time.

关键词： Unmanned Aircraft linear programming Flight Testing Boeing Guidance System Defense Advanced Research Projects Agencies Avionics Systems mixed integer linear programming Unmanned Vehicles Combat Air Vehicle

来源：评论

学校读者我要写书评

暂无评论

A New MILP Formulation and Distributed Protocols for Wireless Sensor Networks Lifetime Maximization

A New MILP Formulation and Distributed Protocols for Wireles...

引用

IEEE International Conference on Communications (ICC)

作者： Stefano Basagni Alessio Carosi Emanuel Melachrinoudis Chiara Petrioli Z. Maria Wang Northeastern University USA Università di Roma La Sapienza Italy

This paper concerns the definition of an analytical model and distributed protocols for determining the routes of a mobile data collector (sink) traveling through the nodes of a wireless sensor network (WSN). The routes are determined with the overall aim of maximizing the network lifetime. The contribution of our work is twofold. First, we introduce a novel mixed integer linear programming formulation for determining the sink's route and the sojourn time at the different "sink sites." The model takes into account realistic parameters such as the maximum distance the sink can travel between sites, different sink mobility rates, as well as the costs to support and perform data routing. Solutions to the model provide the route of the sink as a sequence of sites and the sojourn times at those sites that induce the maximum network lifetime. We then propose the Greedy Maximum Residual Energy (GMRE) protocol for sink mobility. GMRE is distributed and localized, thus being suitable for wireless sensor networking. In GMRE the sink greedily keeps moving toward those areas in the network where there is the most residual energy, as if "drawn" to them. This heuristic is then compared with a very simple and energy-unaware protocol where the next site in the sink route is chosen randomly and uniformly each time the sink moves. Simulation results show that GMRE leads to improvements in network lifetime that are four times as much as the lifetime when the sink is kept static, while balancing energy consumption throughout the network.

关键词： Wireless application protocol Wireless sensor networks Energy consumption Electronic mail Relays Analytical models mixed integer linear programming Costs Routing Delay

来源：评论

学校读者我要写书评

暂无评论

Mapping Task-Graphs on Distributed ECU Networks: Efficient Algorithms for Feasibility and Optimality

Mapping Task-Graphs on Distributed ECU Networks: Efficient A...

引用

IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)

作者： W. Damm A. Metzner F. Eisenbrand G. Shmonin R. Wilhelm S. Winkel Carl von Ossietzky Universität Oldenburg Oldenburg Germany Universität Dortmund Dortmund Germany Universität des Saarlandes Saarbruecken Germany

This mapping problem has to be solved in many application scenarios. In the automotive industry, for example, the implementation of car functions involves distributed task sets running on multiple electronic control units (ECU) with bus-based inter-task communication, a problem we consider in this paper. Our approach is based on mixed integer linear programming (MILP). MILP is concerned with optimizing a linear function subject to a set of linear constraints where some variables are required to be integer. The current state-of-the art method to solve integer programs is the branch-and-cut (B&C) algorithm and several industrial strength solvers are available. We describe a MILP-model for the mapping problem. Handling this model over to a general MILP-solver does not yield satisfactory results in terms of running time. To make the model more efficient we use the above ingredients: we incorporate a primal heuristic, strengthen the model with further inequalities and generate on-demand cutting planes, which violate the current fractional solution. These routines drastically speed up the solution time

关键词： Automotive engineering Communication industry Electronics industry Industrial control Industrial electronics Communication system control Electric variables control mixed integer linear programming Constraint optimization Art

来源：评论

学校读者我要写书评

暂无评论

Joint Range and Load Considerations for Topology Control in Wireless Ad Hoc Networks

Joint Range and Load Considerations for Topology Control in ...

引用

IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON)

作者： Sajjad Zarifzadeh Amir Nayyeri Nasser Yazdani Router Laboratory University of Tehran Tehran Iran

Wireless ad hoc networks are usually composed of tiny and resource constraint devices, which make energy conservation a vital concern of their design. Reducing energy consumption has been addressed through different aspects till now. Topology control (TC) is a well-known approach which tries to assign the transmission ranges of nodes to optimize energy utilization while keeping some network properties like connectivity. However, in current TC schemes, the transmission range of each node is mostly accounted as the exclusive estimator for its energy consumption, while ignoring the amount of data it sends or relays. In this paper, we redefine the problem of topology control regarding both traffic load and transmission range parameters. After proving the NP-hardness of the new problem, we mathematically formulate it as a mixed integer linear programming problem to find the optimal solutions. Then, we introduce two polynomial-time heuristic algorithms to practically solve the problem. Finally, we show the advantages of our proposals through simulations

关键词： Network topology Mobile ad hoc networks Energy consumption Energy conservation Relays Telecommunication traffic mixed integer linear programming Polynomials Heuristic algorithms Proposals

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：