基于SDN的卫星网络多QoS目标优化路由算法

针对传统卫星网络中业务类型多样化导致的网络配置复杂和业务服务质量(quality of service, QoS)无法得到有效保障的问题,研究了基于软件定义网络(software-defined networking, SDN)的卫星网络架构,提出了一种能够满足多种QoS需求的自适应路由算法。首先,建立了软件定义卫星网络多约束条件路由选择优化模型;然后,使用拉格朗日松弛法对模型进行松弛处理;最后,使用梯度法进行迭代求解,搜索出满足带宽、时延、丢包率等多种QoS的最优路径。研究结果表明,该优化算法在QoS满意度方面相比近地轨道卫星路由算法提高了64%,在时延满意度和丢包率满意度方面相比软件定义路由算法提高了28%。     

自适应的无线融断网络路由算法研究

无线融断网络具有长延时、高动态拓扑、链路不稳定等特点,伴随着网络联接缺乏源端到目的端的持续性,为解决网络通信困难的问题,将多头绒泡菌的智能性和自适应性引入,提出一种自适应的无线融断网络路由算法。搭建无线融断网络模型,推导出链路容量的数学表达;设计下一跳节点的选择策略和最佳路由选择策略,实现在融断网络环境下的数据尽力投递。仿真实验表明,该算法能够在网络开销率较低的情况下,达到良好的数据投递,且平均延迟小。     

Distributed Consensus-Based K-Means Algorithm in Switching Multi-Agent Networks

This paper discusses a distributed design for clustering based on the K-means algorithm in a switching multi-agent network, for the case when data are decentralized stored and unavailable to all agents. The authors propose a consensus-based algorithm in distributed case, that is, the doubleclock consensus-based K-means algorithm(DCKA). With mild connectivity conditions, the authors show convergence of DCKA to guarantee a distributed solution to the clustering problem, even though the network topology is time-varying. Moreover, the authors provide experimental results on various clustering datasets to illustrate the effectiveness of the fully distributed algorithm DCKA, whose performance may be better than that of the centralized K-means algorithm.     

Research on performance of ethernet interface in network centric warfare

The concept of network centric warfare (NCW) and its character, high requirement of real-time synchronization are introduced. The distributed equal-node network architecture in NCW is presented. Based on theoretical analysis on ethernet interface performance, this paper presents that forwarding latency between ethernet interface devices is a key influence factor of real-time synchronization in NCW. Ethernet fundamental is briefly introduced. The model between a switch under test (SUT) and a smartbits card is presented and used for two interconnecting switches in NCW. On condition that ignoring the latency of connecting fiber or twisted pairs and processing latency of the smartbits test system, this paper presents that clock frequency tolerance (CFT) between a SUT and a smartbits card is a leading influence factor of forwarding latency of an ethernet switch. The formulae to calculate internal forwarding latency and forwarding latency caused by its CFT are deduced. Theoretical calculation on forwarding latency of an ethernet switch based on the given CFT and test time is implemented. Experimental study on primary forwarding latency and secondary forwarding latency is implemented and forwarding latency between the SUT and the smartbits card is measured, thus testifying the accuracy of the above theoretical analysis that the CFT is a key influence factor of forwarding latency. The measures to satisfy the needs of forwarding latency in NCW are presented.     

标签分割的软件定义飞行自组网控制器智能部署方法

针对当前软件定义飞行自组网中多控制器部署面临的负载不均衡和网络可靠性问题, 提出一种标签分割的控制器智能部署方法。该方法能够在不预设控制器数量的条件下, 根据控制器容量约束和网络结构, 输出最佳控制器数量及部署位置。基于节点自身特征和关联特征赋予节点标签, 根据标签完成控制域划分并通过布谷鸟搜索算法优化划分过程。在此基础上，考虑控制器平均时延、负载差异度和控制域时延波动的影响, 确定控制器部署位置。仿真结果表明，所提算法能在保证网络可靠性的同时有效减少控制器数量, 降低部署成本; 同时, 降低控制器平均时延和负载差异度, 保证各控制域间平均时延的相对平衡, 实现网络均衡。     

A note on the nestedness property for ordered median problems in tree networks

The nestedness property has become an increasingly important means for devising efficient algorithms for network location problems. There have been attempts to explore the nestedness property of network location problems with some special cases of the convex ordered median objectives. However, there is little research on the nestedness property for those problems with the concave ordered median objectives. This paper constructs a tree network T and shows that the nestedness property cannot hold for the concave ordered median problem, which fills a gap in the research on the nestedness property. Finally, the authors pose an open problem on identifying the nestedness property for the continuous strategic ordered median problem.     

Simplifying the nonlinear continuous time-cost tradeoff problem

Equivalent simplification is an effective method for solving large-scale complex problems. In this paper, the authors simplify a classic project scheduling problem, which is the nonlinear continuous time-cost tradeoff problem (TCTP). Simplifying TCTP is a simple path problem in a critical path method (CPM) network. The authors transform TCTP into a simple activity float problem and design a complex polynomial algorithm for its solution. First, the authors discover relationships between activity floats and path lengths by studying activity floats from the perspective of path instead of time. Second, the authors perform simplification and improve the efficiency and accuracy of the solution by deleting redundant activities and narrowing the duration intervals of non-redundant activities. Finally, the authors compare our method with current methods. The relationships between activity floats and path lengths provide new approaches for other path and correlative project problems.     

面向特定应用的片上网络低能耗拓扑生成方法

为解决面向特定应用的片上网络（network on chip, NoC）设计中的低能耗问题,提出基于遗传算法的层次化拓扑生成方法(genetic algorithm based topology generation, GATG)。该方法以降低网络通信能耗为目标,在满足带宽和延时约束下,根据给定应用的通信需求和路由器结构特征,自动将IP核映射到所选路由器单元。同时提出一种基于递归实现的路径构建算法嵌入GATG,用于确定IP核间的通信路径,从而构建路由器之间的链路,最终生成专用的不规则的NoC拓扑结构。实验结果表明,GATG生成结果与采用规则二维Mesh结构相比平均降低能耗46.5％,并可节省52.7％的路由器资源开销。     

A Tight Approximation Algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line

In this paper, the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand. The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint. The authors show that this problem has no polynomial-time algorithm with performance ratio less than 2 on condition that P ≠ NP, and then provide a 2-approximation algorithm.

     

Distributed Consensus-Based <Emphasis Type="Italic">K</Emphasis>-Means Algorithm in Switching Multi-Agent Networks

This paper discusses a distributed design for clustering based on the K-means algorithm in a switching multi-agent network, for the case when data are decentralized stored and unavailable to all agents. The authors propose a consensus-based algorithm in distributed case, that is, the double-clock consensus-based K-means algorithm (DCKA). With mild connectivity conditions, the authors show convergence of DCKA to guarantee a distributed solution to the clustering problem, even though the network topology is time-varying. Moreover, the authors provide experimental results on various clustering datasets to illustrate the effectiveness of the fully distributed algorithm DCKA, whose performance may be better than that of the centralized K-means algorithm.     

Distributed Algorithm for Robust Resource Allocation with Polyhedral Uncertain Allocation Parameters

This paper studies a distributed robust resource allocation problem with nonsmooth objective functions under polyhedral uncertain allocation parameters. In the considered distributed robust resource allocation problem, the (nonsmooth) objective function is a sum of local convex objective functions assigned to agents in a multi-agent network. Each agent has a private feasible set and decides a local variable, and all the local variables are coupled with a global affine inequality constraint, which is subject to polyhedral uncertain parameters. With the duality theory of convex optimization, the authors derive a robust counterpart of the robust resource allocation problem. Based on the robust counterpart, the authors propose a novel distributed continuous-time algorithm, in which each agent only knows its local objective function, local uncertainty parameter, local constraint set, and its neighbors’ information. Using the stability theory of differential inclusions, the authors show that the algorithm is able to find the optimal solution under some mild conditions. Finally, the authors give an example to illustrate the efficacy of the proposed algorithm.     

Multi-facility ordered median problems in directed networks

This paper uses a finite dominating set (FDS) to investigate the multi-facility ordered median problem (OMP) in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS in the node set, which not only generalizes the FDS result provided by Kalcsics, et al. (2002), but also extends the FDS result from the single-facility case to the multiple case, filling an important gap. Then, based on this FDS result, the authors develop an exact algorithm to solve the problem. However, if the number of facilities is large, it is not practical to find the optimal solution, because the multi-facility OMP in directed networks is NP-hard. Hence, we present a constant-approximation algorithm for the p-median problem in directed networks. Finally, we pose an open problem for future research.     

The Dynamics of Two-State Public Opinion Propagation On Signed Networks

The formation of public opinion on the network is a hot issue in the field of complex network research, and some classical dynamic models are used to solve this problem. The signed network is a particular form of the complex network, which can adequately describe the amicable and hostile relationships in complex real-world systems. However, the methods for studying the dynamic process of public opinion propagation on signed networks still require to be further discussed. In this paper, the authors pay attention to the influence of negative edges in order to design a two-state public opinion propagation mechanism suitable for signed networks. The authors first set the interaction rules between nodes and the transition rules of node states and then apply the model to synthetic and real-world signed networks. The simulation results show that there is a critical value of the negative edge ratio.When the negative edge ratio exceeds this critical value, the evolutionary result of public opinion will change from a consistent state to a split state. This conclusion is also consistent with the distribution result of opinions within communities in the signed network. Besides, the research on the network structural balance shows that the model makes the network evolve in a more balanced direction.     

QoS-aware multicast routing protocol for Ad hoc networks

1 .INTRODUCTIONA mobile ad hoc network ( MANET) is a multi-hopwireless network formed by a collection of mobilenodes without the intervention of fixedinfrastructure.Because an Ad hoc network is infrastructure-less andself-organized,it is used to provide i mpromptu com-munication facilities in harsh environments . Typicalapplication areas of mobile ad hoc networkinclude bat-tlefields ,emergency search,rescue sites and data ac-quisitionin remote areas . A mobile Ad hoc networkisalso usef…     

Finding Key Node Sets in Complex Networks Based on Improved Discrete Fireworks Algorithm

Finding out the key node sets that affect network robustness has great practical significance for network protection and network disintegration. In this paper, the problem of finding key node sets in complex networks is defined firstly. Because it is an NP-hard combinatorial optimization problem,discrete fireworks algorithm is introduced to search the optimal solution, which is a swarm intelligence algorithm and is improved by the prior information of networks. To verify the effect of improved discrete fireworks algorithm(IDFA), experiments are carried out on various model networks and real power grid.Results show that the proposed IDFA is obviously superior to the benchmark algorithms, and networks suffer more damage when the key node sets obtained by IDFA are removed from the networks. The key node sets found by IDFA contain a large number of non-central nodes, which provides the authors a new perspective that the seemingly insignificant nodes may also have an important impact on the robustness of the network.     

Distributed quantized consensus for agents on directed networks

Communication bandwidth and network topology are two important factors that affect performance of distributed consensus in multi-agent systems. The available works about quantized average consensus assume that the adjacency matrices associated with the digraphs are doubly stochastic, which amounts to that the digital networks are balanced. However, this assumption may be unrealistic in practice. In this paper, without assuming double stochasticity, the authors revisit an existing quantized average consensus protocol with the logarithmic quantization scheme, and investigate the quantized consensus problem in general directed digital networks that are strongly connected but not necessarily balanced. The authors first derive an achievable upper bound of the quantization precision parameter to design suitable logarithmic quantizer, and this bound explicitly depends on network topology. Subsequently, by means of the matrix transformation and the Lyapunov techniques, the authors provide a testable condition under which the weighted average consensus can be achieved with the proposed quantized protocol.     

Bilevel programming model and solution method for mixed transportation network design problem

By handling the travel cost function artfully, the authors formulate the transportation mixed network design problem (MNDP) as a mixed-integer, nonlinear bilevel programming problem, in which the lower-level problem, comparing with that of conventional bilevel DNDP models, is not a side constrained user equilibrium assignment problem, but a standard user equilibrium assignment problem. Then, the bilevel programming model for MNDP is reformulated as a continuous version of bilevel programming problem by the continuation method. By virtue of the optimal-value function, the lower-level assignment problem can be expressed as a nonlinear equality constraint. Therefore, the bilevel programming model for MNDP can be transformed into an equivalent single-level optimization problem. By exploring the inherent nature of the MNDP, the optimal-value function for the lower-level equilibrium assignment problem is proved to be continuously differentiable and its functional value and gradient can be obtained efficiently. Thus, a continuously differentiable but still nonconvex optimization formulation of the MNDP is created, and then a locally convergent algorithm is proposed by applying penalty function method. The inner loop of solving the subproblem is mainly to implement an all-or-nothing assignment. Finally, a small-scale transportation network and a large-scale network are presented to verify the proposed model and algorithm. This research is supported by the National Basic Research Program of China under Grant No. 2006CB705500, the National Natural Science Foundation of China under Grant No. 0631001, the Program for Changjiang Scholars and Innovative Research Team in University, and Volvo Research and Educational Foundations.     

传感网络低占空比MAC协议同步机制研究

低占空比MAC协议通过节点休眠有效延长了传感网络的寿命,然而同步过程中许多节点监听多个计划,降低了协议的节能效果;同时节点休眠导致数据转发时延大大延长。提出了一种适用于低占空比MAC的新同步机制。基站成为唯一的同步发起者,它周期性地发布同步信息。其他节点仅监听一个计划并广播他们自己的休眠计划,多跳路径上的邻居节点交错监听周期。在一个树型拓扑网络上的仿真试验表明,此同步机制可以在更少能量的条件下进一步减少低占空比MAC的系统时延,提高网络在较重负载下的吞吐量。     

Modeling genetic regulatory networks: a delay discrete dynamical model approach

Modeling genetic regulatory networks is an important research topic in genomic research and computational systems biology.This paper considers the problem of constructing a genetic regulatory network(GRN) using the discrete dynamic system(DDS) model approach.Although considerable research has been devoted to building GRNs,many of the works did not consider the time-delay effect. Here,the authors propose a time-delay DDS model composed of linear difference equations to represent temporal interactions among significantly expressed genes.The authors also introduce interpolation scheme and re-sampling method for equalizing the non-uniformity of sampling time points.Statistical significance plays an active role in obtaining the optimal interaction matrix of GRNs.The constructed genetic network using linear multiple regression matches with the original data very well.Simulation results are given to demonstrate the effectiveness of the proposed method and model.     

Some inverse optimization problems on network

In this paper, the authors consider some inverse problems on network, such as the inverse transport problems with gains (IGTP) and the inverse linear fractional minimum cost flow problem (IFFP). Firstly, the authors give the mathematics model of (IGTP) and an efficient method of solving it under l ₁ norm; Secondly, taking advantage of the optimality conditions, the authors consider the (IFFP) and give a simple method of solving it. Finally, an numerical example test is also developed.