利用改进ILP和二进制穷举择优法的低成本物联网流量多目标路由感知方法

针对无线网络不能为多样化应用需求提供支持及卸载移动通信核心成本较高的问题,提出了一种改进整数线性规划模型(IILP)结合二进制穷举择优法的低成本混合物联网流量多目标路由感知方法。首先,基于IILP对混合物联网流量路由感知进行建模,获得准确的能量感知模型;其次,采用多目标MAXI路由感知算法对多目标路由感知模型进行了求解,降低了流量路由求解的延时;最后,采用二进制穷举择优法对流量路由感知的吞吐量进行扩展。仿真实验表明,与现有算法相比,提出方法降低了求解的延时,提高了流量的吞吐量,减少了流量的丢包率,同时还降低了混合物联网多目标路由感知的成本。     

Maximal matching polytope in trees

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.     

Ad Hoc中基于动态规划的多约束QoS路由协议

对于Ad Hoc网络中多约束QoS求解问题,启发式算法的局限性在于寻路时间长。为此提出一种基于动态规划的多约束QoS路由协议,利用动态规划算法解决判据的最优化问题。在路由请求阶段寻求满足数据带宽需求的多条路由,目的节点应用动态规划算法寻求时延最优的路由。从相关的分组结构和路由流程两个方面对其进行了描述。最后通过仿真从平均端到端时延、分组投递率以及路由开销三个方面与传统的DSR路由进行对比,对于大规模Ad Hoc网络,能够明显提高网络的性能。     

基于VNF间性能干扰的服务请求调度策略

网络功能虚拟化(NFV)技术是当今研究的热点技术之一。目前的虚拟网络功能(VNF)放置方法大都忽视了同位间VNF即处在同一个物理机中的虚拟网络功能,对硬件资源的竞争所形成的干扰问题,会导致网络吞吐量下降。针对此问题,该文建立了以最大化网络吞吐量为目标的混合整数线性规划模型,设计了一个两步调整策略。第一步设计了组合放置算法(CAPA),将资源需求互补的虚拟网络功能进行组合放置;第二步根据不同虚拟网络功能对数据流量的处理特性,设计了流量感知算法(TAA)进行服务请求调度,进一步缓解了在大的数据流量场景下,底层硬件资源竞争更加激烈使得干扰增强的问题。实验结果表明,该文提出的两步调整策略,与忽视干扰因素的一般策略相比提高了网络吞吐量。     

Minimum cost multiple multicast network coding with quantized rates

In this paper, we consider multiple multicast sessions with intra-session network coding where rates over all links are integer multiples of a basic rate. Although having quantized rates over communication links is quite common, conventional minimum cost network coding problem cannot generally result in quantized solutions. In this research, the problem of finding minimum cost transmission for multiple multicast sessions with network coding is addressed. It is assumed that the rate of coded packet injection at every link of each session takes quantized values. First, this problem is formulated as a mixed integer linear programming problem, and then it is proved that this problem is strongly NP-hard on general graphs. In order to obtain an exact solution for the problem, an effective and efficient scheme based on Benders decomposition is developed. Using this scheme the problem is decomposed into a master integer programming problem and several linear programming sub-problems. The efficiency of the proposed scheme is subsequently evaluated by numerical results on random networks.     

无线传感器网络中传输范围调整的动态规划算法

研究在无线传感器网络中如何选择活动的路由节点及其传输范围,以有效节省能量的消耗。在节点随机布设的线性网络中,当网络传输流量一定的条件下,提出了三种路由节点选择及其传输范围调整算法,获得最优无线传输范围与通信流量之间的关系,数值计算证实了其中的动态规划算法可以选择到最优能量消耗的路由节点及其传输范围。     

能量捕获无线传感器网络中速率自适应路由算法

能量捕获无线传感器网络是无源感知技术中非常重要的一类,它能够有效解决节点能量受限的问题,保持网络运行的持续性.现有的路由方法并未充分利用节点的能量捕获特性,也没有考虑到链路的成功收包率和节点的传输速率.为进一步提高网络的性能,提出了一种结合链路成功收包率的速率自适应路由算法.通过对节点的剩余能量和链路的成功收包率进行建模,给出了一个节点可作为路由中继节点所需要满足的两个条件;基于优化方程,为传输路径上的每一跳节点自适应配置时延最小化的传输速率;提出路由发现步骤来找出端到端传输时延最小的传输路径.实验结果表明,相比于固定传输速率的路由算法,所提算法所得到的传输路径具有较低的端到端传输时延和较高的吞吐率.     

DMEERP: A dynamic multi-hop energy efficient routing protocol for WSN

Balancing the energy efficiency and path reliability is the biggest task in Wireless Sensor Networks (WSNs). The existing schemes fail to improve the network performance. In this research, a dynamic Multi-hop Energy Efficient Routing Protocol (DMEERP) is proposed to balance the path reliability ratio and energy consumption. It contains three sections. In first section, network model and basic assumptions were made for cluster creation and multi-hop route establishment. The Super Cluster Head (SCH) stores and maintains all records of CH and cluster members. The node activation and weight factor are estimated to obtain new cluster head if existing fails. In second section, path reliability ratio is estimated for routing the packets quickly without making more packet loss. In third section, energy model is implemented based on channel capacity model. The simulation analysis are made using network simulator (NS 2.33) in terms of packet delivery ratio, network lifetime, data flow, energy consumption, path reliability ratio, control overhead and delay etc.     

Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

双向路径重选的自组网负载均衡路由协议

基于跨层负载感知和双向路径重选的自纽网负载均衡路由协议（CLBLR）在路由发现阶段和路由维护阶段，将整个路径中各节点MAC层的总平均估计时延和路径总业务流负载结合起来，共同作为路由选择和路由调整的重要依据，通过双向路径重选方法实现最优路径选择和网络业务流的均衡分布和均衡传输．协议通过禁止中间节点对路由请求进行应答和阻止不必要的路由请求分组，经由重负载中间节点转发，以保证路由发现时能够利用最新负载信息，并避免了节点在重负载情况下成为新建路由的中间节点，使协议具有一定的拥塞控制功能，以间接的方式实现了请求接纳控制．上述措施使分组传输路由很好地避免了拥塞节点，减少了网络瓶颈对网络性能的影响．仿真表明，CLBLR在分组丢失率、平均端到端时延和路由附加开销等方面具有良好性能，其优良的分布式控制特征能适应自组网的动态环境．     

Solving diameter‐constrained minimum spanning tree problems by constraint programming

The diameter‐constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is bounded from above by a given constant. This problem typically models network design applications where all vertices communicate with each other at a minimum cost, subject to a given quality requirement. We propose alternative formulations using constraint programming that circumvent weak lower bounds yielded by most mixed‐integer programming formulations. Computational results show that the proposed formulation, combined with an appropriate search procedure, solves larger instances and is faster than other approaches in the literature.     

Exact solutions of some optimization problems of transport logistics

A problem for constructing the shortest cyclic route that ensures homogeneous cargo is delivered from producers to consumers by a transport vehicle of limited capacity is considered. Formalizations in the form of Boolean quadratic programming and linear integer programming problems are given. Comparative analysis of the efficiency of three exact algorithms is performed. The problem of finding the minimal admissible capacity of the transport vehicle is considered as an auxiliary problem. Dependence of the length of the optimal route on the capacity of the transport vehicle is studied experimentally.     

Proportional Fairness Based Energy Efficient Routing in Wireless Sensor Network

Wireless Sensor Network (WSN) is an independent device that comprises a discrete collection of Sensor Nodes (SN) to sense environmental positions, device monitoring, and collection of information. Due to limited energy resources available at SN, the primary issue is to present an energy-efficient framework and conserve the energy while constructing a route path along with each sensor node. However, many energy-efficient techniques focused drastically on energy harvesting and reduced energy consumption but failed to support energy-efficient routing with minimal energy consumption in WSN. This paper presents an energy-efficient routing system called Energy-aware Proportional Fairness Multi-user Routing (EPFMR) framework in WSN. EPFMR is deployed in the WSN environment using the instance time. The request time sent for the route discovery is the foremost step designed in the EPFMR framework to reduce the energy consumption rate. The proportional fairness routing in WSN selects the best route path for the packet flow based on the relationship between the periods of requests between different SN. Route path discovered for packet flow also measure energy on multi-user route path using the Greedy Instance Fair Method (GIFM). The GIFM in EPFMR develops node dependent energy-efficient localized route path, improving the throughput. The energy-aware framework maximizes the throughput rate and performs experimental evaluation on factors such as energy consumption rate during routing, Throughput, RST, node density and average energy per packet in WSN. The Route Searching Time (RST) is reduced using the Boltzmann Distribution (BD), and as a result, the energy is minimized on multi-user WSN. Finally, GIFM applies an instance time difference-based route searching on WSN to attain an optimal energy minimization system. Experimental analysis shows that the EPFMR framework can reduce the RST by 23.47% and improve the throughput by 6.79% compared with the state-of-the-art works.     

无线传感器网络中基于能量效率的多路径路由算法

针对无线传感器网络节点能量受限的特点,本文提出了一种能量有效、负载均衡的多路径路由算法(EMR)。该算法在按需路由协议AODV基础上,不单纯以最小跳数或者最小时延作为路由选择依据,充分考虑到了路由的能量消耗最小化,避开剩余能量过低的节点,数据沿着最小跳数或路径关键能量比较高的路径传输,降低了网络的能量消耗,也避免关键节点的过量负载。分析与仿真结果表明,与AODV协议相比较,EMR具有更好的分组投递率、端到端时延,推迟了网络中出现死亡节点的时间,从而延长了网络生命周期。     

Operational Optimization for Microgrid of Buildings with Distributed Solar Power and Battery

Improving building energy efficiency is significant for energy conservation and environmental protection. When there are multiple buildings with solar power generation and batteries connected in a microgrid, coordinating the distributed energy supply and consumption may substantially improve the energy efficiency. We consider this important problem in this paper and make the following three major contributions. First, we formulate the operation optimization of a microgrid of buildings as a two‐stage stochastic programming problem. Second, the problem is transformed into a stochastic mixed‐integer linear programming. Then the scenario method is used to solve the problem. Third, case studies of a university campus is presented. The numerical results show that coordinating the distributed solar power and battery can reduce the operational cost of the microgrid.     

A novel optimization-based bandwidth-aware minimum power multicast routing algorithm in green wireless networks

Multicast routing in wireless networks that possess the wireless multicast advantage could significantly reduce the power and energy consumption. However, this kind of multicast routing that only addresses the transmission radius coverage might not be able to meet the bandwidth requirement of the users. As a result, additional transmissions are required to incur more energy consumption and carbon dioxide emissions that make existing algorithms not applicable to bandwidth constrained applications. In this paper, for the first time, we address the bandwidth aware minimum power multicast routing problem in wireless networks where the objective function is to minimize the total power consumption subject to the users?? bandwidth requirements. This problem is a challenging cross-layer design problem that requires seamless and sophisticated integrated design in the network layer (multicast routing) and physical layer (bandwidth-aware wireless transmission and power control). We first formulate this problem as a mixed integer linear programming problem and then propose a Lagrangian relaxation based algorithm to solve this problem. Numerical results demonstrate that the proposed approach is a sound green networking algorithm that outperforms the existing power efficient multicast routing approaches under all tested cases, especially in large bandwidth request, fine radius granularity, large group size and sparse network.     

适于估计OD矩阵的交通检测点的最优分布

讨论了适于估计起迄点出行分布矩阵(OD矩阵)的交通检测点的合理分布问题.根 据检测点应当满足的规则,建立了关于检测点分布的非线性规划模型.在已知极点问转移概 率的前提下,将检测点的分布问题描述成一个平均报酬Markov决策过程,并通过转化为一 个等价的整数线性规划问题来求解.最后实例结果表明该模型是有效的、合理的.     

Gamma deployment problem in grids: hardness and new integer linear programming formulation

Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP‐complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap.     

A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem

In this paper, the simultaneous order acceptance and scheduling problem is developed by considering the variety of customers’ requests. To that end, two agents with different scheduling criteria including the total weighted lateness for the first and the weighted number of tardy orders for the second agent are considered. The objective is to maximize the sum of the total profit of the first and the total revenue of the second agents’ orders when the weighted number of tardy orders of the second agent is bounded by an upper bound value. In this study, it is shown that this problem is NP-hard in the strong sense, and then to optimally solve it, an integer linear programming model is proposed based on the properties of optimal solution. This model is capable of solving problem instances up to 60 orders in size. Also, the LP-relaxation of this model was used to propose a hybrid meta-heuristic algorithm which was developed by employing genetic algorithm and linear programming. Computational results reveal that the proposed meta-heuristic can achieve near optimal solutions so efficiently that for the instances up to 60 orders in size, the average deviation of the model from the optimal solution is lower than 0.2% and for the instances up to 150 orders in size, the average deviation from the problem upper bound is lower than 1.5%.     

自组网中一种基于跨层负载感知的按需负载均衡路由

本文提出了一种新的基于跨层负载感知的自组网负载均衡路由协议（CLLOR）。CLLOR在路由发现阶段和路由维护阶段将整个路径中各节点MAC层的总平均估计时延和路径总业务流负载结合起来共同作为路由选择和路由调整的重要依据,以实现网络业务流的均衡分布和均衡传输。协议通过禁止中间节点对路由请求进行应答和阻止不必要的路由请求分组经由重负载的中间节点转发,以保证路由发现时能够利用最新的负载信息,并避免了节点在重负载情况下成为新建路由的中间节点,使得协议具有一定的拥塞控制功能,以间接的方式实现了请求接纳控制。通过上述措施,可以很好地避免网络中出现拥塞节点,减少了网络瓶颈对网络性能的影响。仿真表明,CLLOR在分组丢失率、平均端到端时延和路由附加开销等方面具有良好的性能,其优良的分布式控制特征能适应自组网的动态环境。