Search space reduction of asynchrony immune cellular automata

Natural Computing - We continue the study of asynchrony immunity in cellular automata (CA), which can be considered as a generalization of correlation immunity in the case of vectorial Boolean...     

On localized control in QoS routing

In this note, we study several issues in the design of localized quality-of-service (QoS) routing schemes that make routing decisions based on locally collected QoS state information (i.e., there is no network-wide information exchange among routers). In particular, we investigate the granularity of local QoS state information and its impact on the design of localized QoS routing schemes from a theoretical perspective. We develop two theoretical models for studying localized proportional routing: one using the link-level information and the other using path-level information. We compare the performance of these localized proportional routing models with that of a global optimal proportional model that has knowledge of the global network QoS state. We demonstrate that using only coarser-grain path-level information it is possible to obtain near-optimal proportions. We then discuss the issues involved in implementation of localized proportional routing and present some practical schemes that are simple and easy to implement     

Precomputation for intra-domain QoS routing

Quality-of-service routing (QoSR), seeking to find a feasible path with multiple constraints, is an NP-complete problem. We propose a novel precomputation approach to multi-constrained intra-domain QoS routing (PMCP). It is assumed that a router maintains the link state information of the entire domain. PMCP cares each QoS weight to several degrees, and computes a number of QoS coefficients uniformly distributed in the multi-dimensional QoS metric space. Based on each coefficient, a linear QoS function is constructed to convert the multiple QoS metrics to a single QoS value. We then create a shortest path tree with respect to the QoS value by Dijkstra’s algorithm. Finally, according to the multiple coefficients, different shortest path trees are calculated to compose the QoS routing table. We analyze linear QoS functions in the QoS metric space, and give a mathematical model to determine the feasibility of a QoS request in the space. After PMCP is introduced, we analyze its computational complexity and present a method of QoS routing table lookup. Extensive simulations evaluate the performance of the proposed algorithm and present a comparative study.     

一种基于模糊塔的QoS单播路由选择算法

综合考虑用户服务质量QoS需求和网络提供方收益的单播路由算法．给定用户请求类别和收费原则,通过建立网络提供方收益模型来确定针对每一类请求的概率收益．在此基础上,利用模糊塔,求出两网络节点之间既满足用户服务质量需求又试图最大化网络提供方概率收益的路由。仿真结果表明,算法是可行的和有效的。     

基于可用性的QoS选路研究*

基于可用性的QoS选路(availability-based-QoS routing,AQR)是个复杂的问题。将AQR分为两类,第一类AQR只需要搜索从源点到终点满足QoS约束条件的工作路径;第二类AQR问题除了搜索工作路径,还需要搜索这个工作路径的备份路径。已有文献对第一类AQR问题研究比较多;对于多约束的第二类AQR问题,则研究得比较少。指出了第二类问题虽然比较复杂,但可以借助于第一类问题的算法经过一些策略而得到解决;该思路可以有效利用已有文献提出的关于第一类AQR的现成算法,从而解决第二类AQR问题     

Efficient hierarchical QoS routing in ATM networks

For reducing network information to achieve scalability in large ATM networks, ATM Private Network-to-Network Interface (PNNI) adopts hierarchical routing. Consequently, although routing complexity is significantly reduced, numerous issues in PNNI routing require further study to achieve more efficient, accurate, scalable, and QoS-aware routing.Several methods are adopted herein to achieve efficient, scalable, and QoS-aware ATM PNNI routing. First, an efficient aggregation scheme, referred to as Asymmetric Simple, is proposed. The aggregated routing information includes available bandwidth, delay and cost. Second, two approaches for defining link costs are investigated, namely, the Markov Decision Process (MDP) approach and the Competitive On-Line (COL) routing approach, and these are compared with the Widest Path (WP) approach. Finally, a dynamic update policy, referred to as the dynamic cost-based update (DCU) policy, is proposed to improve the accuracy of the aggregated information and the performance of hierarchical routing, while decreasing the frequency of re-aggregation and information distribution.Simulation results demonstrate that the proposed Asymmetric Simple aggregation scheme yields very good network utilization while significantly reducing the amount of advertised information. Between these two link cost functions, the MDP approach provides a systematic method of defining call admission function and yields better network utilization than the COL approach. The proposed DCU policy also yields an enhanced network utilization while significantly reducing the frequency of re-aggregation and the amount of distributed aggregation information.     

Virtual Strategy QoS routing in satellite networks

Satellite network users want to unify different satellites to enhance the quality-of-service (QoS) stability of the satellite networks and select feasible paths through different networks to feed different applications. Unfortunately, the state of affairs is that different applications need to use several different application programming interfaces and to design different protocols on how and when to use a specific network. This is troublesome and error-prone as the application programming interfaces vary a lot. In this paper, we design a Virtual Strategy in satellite network based on which a QoS routing service scheme is then proposed. We analyze why applications should use and benefit from Virtual Strategy. This Virtual Strategy is a middleware solution that enables seamless usage of services from different satellite network parts. And then, the supporting QoS routing solution enables the committed QoS services over Virtual Strategy. Finally, we provide a comparison between the previous satellite networks and our work. The simulation results show that our Virtual Strategy QoS routing scheme demonstrates dominated performances under complex architecture.     

一个效率可观的启发式多约束QoS路由算法

提出的MWA_MCP(maximal weight amputation for multi-constrained problem)算法,充分利用了BFS(bread first search)算法计算复杂度简单的特点,使用BFS搜索QoS路径.MWA_MCP在搜索过程中有选择地去掉QoS性能差的边,即权重较大的边将在搜索中有策略地被去掉.与仿真的几个算法相比,MWA_MCP体现了较高的路由性能.     

多约束路由的简单求解方法

已有多约束路由问题的算法都相当复杂,其步骤多、处理开销大,这些都会给QoS的实际应用带来很大的限制.ATC(additive-to-concave)算法把加性参数转换为瓶颈性参数,使用直观、简单的方法找到从源点到终点的路径.该方法是QoS多约束路由问题算法中最简单的方法,并且性能较好.     

无线多媒体传感器网络能量均衡的QoS路由算法

为保障能量受限的无线多媒体传感器网络(WMSNs)多服务质量(QoS)需求,提出了一种能量均衡的QoS路由(EBQR)算法。该算法通过蚁群优化将网络带宽、时延、丢包率和能量等因素作为目标函数,并根据函数值大小动态调整蚁群信息素的挥发系数和浓度增量,提供网络业务中满足不同QoS需求的最优路径。仿真结果表明:与AntWMSNs算法和ASAR算法相比,EBQR算法平均端到端时延降低了16%,丢包率减少22%,生命周期延长了近50%,有效实现了网络中节点能耗的均衡性。     

QoS routing based on genetic algorithm

In this paper, the requirements of routing due to the multimedia applications are briefly discussed. In order to solve the QoS constrained routing effectively and efficiently, the scheme of routing based on a genetic algorithm (GA) is proposed after the analysis of related works. Then the QoS routing algorithms for unicast and multicast based on improved GA are described. Finally, the results of the simulations and the comparison of these results are given.     

一种用于移动自组控制网络的QoS路由

为更好地将移动自组网络用于网络控制系统（NCS）,结合NCS的网络特性,提出了一种基于链路信号质量的QoS路由算法。主要QoS机制包括根据接收信号强度选择较稳定的路由;用Hello报文广播节点的预留带宽;中间节点为所有受影响的数据流修复路由、目的节点向源节点广播路由修复报文进行路由修复。NS2仿真表明当节点移动性强时,该QoS路由算法可有效减少网络的平均端到端时延和丢包率,提高控制系统稳定性。     

基于网络可靠性指标的QoS路由算法

针对网络链路的可靠性在网络设计中的重要性,提高网络中所选路径的可靠性,提升业务性能,提出了一种基于网络可靠性指标的路由算法(BRI).该算法综合考虑了链路的可靠性,带宽等方面的因素,对网络链路的可靠性进行了深入的研究,找出了能提升业务性能、提高可靠性的路由.建立了网络拓扑结构的数学模型,描述了具体的路由算法,最后给出了数值仿真实例.仿真结果表明,算法在提高所选路径的可靠性、提升业务性能,有效利用网络资源等方面是可行的和有效的.     

MANET路由中的链路测量及QoS协议实现

MANET的节点资源受限等特点给QoS路由设计提出了诸多挑战。在研究无线网络流量特性的基础上,提出了基于自相似特性的链路测量及QoS路由协议（Link Prediction based on self-similarity and QoS Routing Protocol,LPQRP）。LPQRP协议使用小波分析方法估计自相似特性唯一参数Hurst值,并利用Hurst值对网络性能进行估计,以测量结果作为QoS路由约束条件,以此方式优化了路由选择,提高了测量精度,有效提高了路由QoS保证。给出了LPQRP协议的设计过程,提出抖动因子等机制进一步完善了LPQRP协议。仿真结果显示,LPQRP协议能很好地适应MANET特性,有效优化数据传输路径,均衡网络资源,提高了网络的健壮性,减少了资源损耗。     

一种启发式算法在多受限QoS路由中的研究

随着互联网的广泛应用,网络服务质量(QoS)保证技术显得越来越重要,为了保证网络服务质量,希望根据多个QoS约束参数来选择可行路由。一般说来,多受限路径优化问题是一个NP完全问题,因此在多项式时间复杂度里不能解决该问题,针对这个问题,在启发式算法的基础上,提出一种改进扩展Bellman-Ford最短路径算法(MEBF),将NP完全问题简化为在多项式时间复杂度里能解决的问题。模拟的结果表明,该算法有良好的运行效率和QoS路由成功率。     

Multi-robot navigation based QoS routing in self-organizing networks

The technical development drives the future networks to become large-scale, heterogeneous, and dynamic. Bio-inspired networking can help reduce the time-space complexity of the complex network. Due to the good features such as self-organization and self-management, self-organizing network (SON) will most probably be a priority choice for the next generation network. In this paper, a swarm intelligence based Quality of Service (QoS) routing protocol is proposed for SON. The inaccurate routing and QoS information is described with fuzzy mathematics whilst the utilities of both the user and the network service provider are considered by applying game theory. Based on the multi-robot navigation algorithm, the protocol is able to search a routing path which can satisfy the user QoS requirements and achieve the Pareto optimal utilities of the user and the network service provider under Nash equilibrium. The proposed protocol is implemented and evaluated by extensive simulation experiments. The results show that it beats both other swarm intelligence based routing protocols and the traditional Dijkstra algorithm based routing protocol. The searched routing paths support the win–win effect for both the user and the network service provider.     

一种基于QoS的VANETs多路径路由协议的设计*

为显著提高路由决策性能,在信息熵的基础上提出了用熵值定量描述链路稳定性的算法;同时综合考虑用户带宽的个性化需求,在多路径路由协议(AOMDV)的基础上设计出一种适用于城市车载Ad hoc网络的QoS路由协议BLS-AOMDV。理论分析论证了BLS-AOMDV协议的有效性及可行性。基于NS2的仿真结果表明,新协议在丢包率、时延、路由开销上都要优于传统的AOMDV多路径路由协议,因此更加适合于城市VANETs应用范畴。     

MANET中一种新QoS路由技术的研究

移动AdHoc网络（MANET）支持QoS保证的能力,受限于无线介质的带宽和节点的移动特性。由于节点的移动,网络拓朴频繁发生变化,一旦节点移动,当前的路由就很容易失效,从而造成通讯中断,这种情况就是链路失效。QoS路由是MANET获得端到端QoS保证的第1步。然而,拓朴变化造成的链路失效状况的存在,使得路由的可靠性对于QoS路由而言非常重要。为使链路失效造成的影响最小,找到生存时间长并且可靠性高的路由就显得尤为重要。提出了一种在MANET中支持Oos路由,并能较好解决链路失效状况的方案。该方案定义了一种新机制,在执行时类似表驱路由协议,通过利用主路径上被共享的邻居节点信息,为主路径上各个独立的子路径预备了可替换的路径。     

移动自组网QoS组播路由协议的研究

针对已有的移动自组网中QoS路由协议进行了分析比较,提出了一种基于逻辑超立方体的虚拟动态骨干网模型以支持QoS组播通信。该模型具有高可用性和负载均衡的特性，而这两种特性是在移动自组网中提供QoS保证的重要前提。基于该模型又设计了一种新颖的基于逻辑位置信息的QoS组播路由算法：自路由，模拟结果显示该算法性能良好，具有延迟小、抖动小、容错性强的特点。