基于PSO算法和移动Agent的WSN路径优化研究

研究了基于PSO(particle swarm optimizing)算法对无线传感器网络中移动Agent迁移路径进行优化的方法.针对传统C/S模型网络中传感器节点需要直接发送数据给Sink节点导致节点能量消耗过大等问题,提出一种采用移动Agent根据路径选择访问节点并将融合后的数据发送给Sink节点的方法,并给出了一种通过PSO算法对路径进行优化的改进方法.实验证明:该方法能够有效降低网络能耗和提高网络生存时间.     

一种评价通信网节点重要性的新方法——节点孤立法

提出了一种评价通信网节点重要性的新方法--节点孤立法,并提出了节点核度积的概念,认为通信网中最重要的节点是孤立后所对应的节点核度积最大的节点.该方法考虑了网络的连接状况,并且动态地考虑了网络中所有节点相互通信的最短路径总长度的增加值.该方法是基于全网性能对节点重要性进行评价,通过比较节点的核度积,判断通信网中任意两个节点的相对重要性,而且使用了一种模2的矩阵运算方法,可以快速得到节点通信的最短路径.理论分析和仿真实验结果表明,该方法的计算复杂度和对节点重要性评价的准确性优于其它算法.     

基于网络传输特性的链路重要性评价方法

提出了一种基于网络传输特性的链路重要性评价方法,根据链路在网络所有节点相互通信的最短路径中的使用频度来评价链路重要性,最重要链路的使用频度最高.该方法不需要像目前的链路重要性评价方法那样进行链路收缩和删除,直接反映了链路对整个网络通信的贡献大小,可以判断通信网中任意两条链路的相对重要性.算法分析和实验仿真表明,文章算法克服了目前的评价方法存在的问题,给出了更直观合理的通信网链路重要性评价准则.     

高可靠性煤矿井下火源无线预警监测系统

鉴于无线ZigBee协议传输数据率低、距离短,为进行煤矿井下大范围高密度火源监测任务,设计一种高可靠性煤矿井下火源无线预警监测系统。在井下煤自燃隐蔽区域布置感温电缆,利用WaveMesh移动自组网协议多跳网络并行传递数据,根据节点路径选择算法选择传输的最佳路径,通过光纤冗余环网传输至监测终端。该系统以可靠性、健壮性和易移植性为设计原则,针对硬件抗干扰和防爆,射频转发相邻节点数据并设置避让机制,WIFI模块或RS485模块及接口模块二选一通信,光纤冗余环网传输数据。经试验表明,无线传感网络最大通信距离为37 m。采用WaveMesh多径路由协议,组成多跳网络在不同路由间自由切换,能够充分利用无线信号的冗余性。     

车载自组织网络信息流量特性分析

为了揭示车载自组织网络动态拓扑特性,预测车载自组织网络行为和缓解网络拥堵,本文从微观角度分析了信息流量分布的一般特性,研究了在不同交通需求下车载自组织网络信息流量分布特性及信息流量与节点度值之间的关系.首先提出度、度分布指数与信息流量的关系,用复杂网络理论以静态、动态两种方式建立无容量限制的无标度网络模型,采用数值模拟实验和仿真实验方法讨论了参数变化时车载自组织网络信息流量变化规律;其次,借助非线性动力学理论研究了考虑容量限制的信息流量分布特性.研究结果表明,信息流量分布指数是无标度网络的通用特征参数,度值大的节点对网络影响较大,传播信息更快,信息流量与度值之间满足幂律分布规律;当信息流量需求增大时,Hub节点可能负担过重,许多信息流量可能会选择其他节点避免与Hub节点连通,这时较小度值的节点承担这部分信息流量.     

基于IEEE1451.5的ZigBee智能传感器即插即用性能优化

为提高基于IEEE 1451.5网络化智能传感器即插即用接口性能,以ZigBee无线智能传感器为对象,研究基于定期关联匹配通信机制传感器即插即用性能优化.通过简化TEDS数据结构,减小无线智能传感器即插即用识别时间并提高识别率;提出基于ZigBee节点邻居表与节点特性参数的ZigBee路由优化措施,实现无线传感接口即插即用数据最优路径传输.实验结果表明:优化后数据传输效率及网络实时性有较大提高,数据传输平均跳数减少42.9％,平均时延降低28.1％.     

Dijkstra改进算法在地震救援中的应用

讨论关于地震救援机器人行走避障的最短路径问题.首先用了Dijkstra最短路径的改进算法,得出其最短路径.但由于这样得出的路径往往会有很多迂回,所以又对其进行一定的优化,最终得到一条较为合理的路径,达到省时和运算代价少的目的.     

RMS中工件路径网络生成方法

利用图论建立RMS中工件路径网络生成模型。给出设备物理布局生成的3种算法：设备物理规划布局算法、基于二次布置问题(QAP)模型的VMC设备物理布局算法以及已有设备物理布局算法。给出AGV路径网络生成算法、AGV路径网络生成改进算法、可替代路径网络生成算法,包括节点间最短路径寻找子算法、路径网络预处理子算法。算法的输入为表示重构对象节点间距离信息的距离矩阵文件和表示某生产周期多工艺路线的流量文件,输出为优化的路径网络。用Visual C 实现了以上算法,实例测试验证了算法的正确性。     

基于线性规划的机器人避障问题

机器人避障最短路径及最短时间路径其实就是研究具有圆形限定区域的最短路径的问题,主要研究机器人在有若干个障碍物一个区域中,由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点的两种情形。通过分析我们可以得出最短路径是由两部分组成的:一部分是在一个平面两点之间的最短路即直线路径,另一部分是障碍物区域的部分边界,这两部分是相切连接的。除此之外我们还发现最小转向曲率半径和障碍物区域大小的浮动对结果都有影响。根据这个结果,可以得出最短路径一定是由直线和圆弧做组成,为此可以建立线圆结构模型,这样不管障碍物有多少,路径有多复杂,我们都可以将路径划分为若干个这种线圆结构来求解。对于路径当中经过障碍物再到达目标点的状况,采用两种方案,一种是在障碍物拐点和节点都采用最小转弯半径的形式,另一种是适当扩大障碍物拐点处的转弯半径,使得机器人能够尽大可能沿直线通过路径中的障碍物到达目标点。建立最优化模型对两种方案分别进行求解。     

机械振动WSNs子带多阶层自适应量化数据压缩方法EI北大核心CSCD

针对资源受限的机械振动无线传感器网络传输大量振动数据时导致的内存空间消耗大及传输效率低等问题,提出一种子带多阶层自适应量化数据压缩方法。首先,传感器节点对原始数据进行分块离散余弦变换以确保子带能量集中;然后,采用子带多阶层自适应量化方法对分块变换数据进行量化以减少数据失真,提高重构数据精度;最后,为进一步提升数据的压缩性能和效率,对量化数据进行2 bit过滤游程算术编码处理。将提出的方法与其他数据压缩方法进行对比以验证该方法的性能,试验结果表明,该方法可以在资源受限的机械振动无线传感器网络节点中获得良好的压缩效果,对提高大量振动数据传输效率有重要意义。     

A network-wide exact optimization approach for multiobjective routing with path protection in multiservice multiprotocol label switching networks

A multiobjective routing model for multiprotocol label switching networks with multiple service types and path protection is presented in this article. The routing problem is formulated as a biobjective integer program, where the considered objectives are formulated according to a network-wide optimization approach, i.e. the objective functions of the route optimization problem depend explicitly on all traffic flows in the network. A disjoint path pair is considered for each traffic trunk, which guarantees protection to the associated connection. A link-path formulation is proposed for the problem, in which a set of possible pairs of paths is devised in advance for each traffic trunk. An exact method (based on the classical constraint method for solving multiobjective problems) is developed for solving the formulated problem. An extensive experimental study, with results on network performance measures in various randomly generated networks, is also presented and discussed.     

一种联合优化的水声通信网路由算法设计

针对传统的无线网络路由建立算法在水下小型网络中时延及能耗代价高的问题,提出了改进的DSDV(Destination Sequenced Distance Vector)路由过程,并在此基础上设计出与拓扑结构、MAC层联合优化的算法。该算法建立了以改进的DSDV路由建立时间、能耗及路由信息的完整性为代价函数,以MAC层的包长度、包间隔、拓扑结构中的点和边数等为矢量参数的数学模型,并结合无向图的广度优先搜索算法及最短路径算法,提出了在上述矢量参数条件下代价函数的最优化设计,形成一套适用于小规模区域性观测应用背景的水声通信网的路由建立方法。仿真结果表明,在相同的物理层条件下,联合优化的算法与未优化的DSDV相比,在相同的时间内建立完整的全网路由的概率最大可提高30%。     

Efficient Routing Protection Algorithm Based on Optimized Network Topology

Network failures are unavoidable and occur frequently. When the network fails, intra-domain routing protocols deploying on the Internet need to undergo a long convergence process. During this period, a large number of messages are discarded, which results in a decline in the user experience and severely affects the quality of service of Internet Service Providers (ISP). Therefore, improving the availability of intra-domain routing is a trending research question to be solved. Industry usually employs routing protection algorithms to improve intra-domain routing availability. However, existing routing protection schemes compute as many backup paths as possible to reduce message loss due to network failures, which increases the cost of the network and impedes the methods deployed in practice. To address the issues, this study proposes an efficient routing protection algorithm based on optimized network topology (ERPBONT). ERPBONT adopts the optimized network topology to calculate a backup path with the minimum path coincidence degree with the shortest path for all source purposes. Firstly, the backup path with the minimum path coincidence with the shortest path is described as an integer programming problem. Then the simulated annealing algorithm ERPBONT is used to find the optimal solution. Finally, the algorithm is tested on the simulated topology and the real topology. The experimental results show that ERPBONT effectively reduces the path coincidence between the shortest path and the backup path, and significantly improves the routing availability.     

Load balancing in the provisioning of hose model virtual private networks with multi-path routing

Load balancing in the provisioning of virtual private network (VPN) service in the hose model is studied. Single-path routing and tree routing for the hose model tend to aggregate bandwidth reservations on a small number of links, thus leading to congestion problems in service provider networks. If the link capacity is depleted as a result of improper routing, all future non-VPN traffic will be blocked. We propose a novel multi-objective multi-path (MOMP) routing linear program with the maximum fraction of traffic on a path (MFTP) constraint to solve the problem. The MOMP routing algorithm is able to reduce the bandwidth reservation on the most loaded link by as much as 50%, thus effectively alleviating the potential congestion problems in service provider network. The MFTP constraint provides a guarantee of the availability of multiple paths for each VPN endpoint pair. Further reduction of the bandwidth reservation can be achieved depending on the MFTP value. This is highly significant.     

Routing of Uncertain Traffic Demands

Due to the success of the Internet and the diversity of communication applications, it is becoming increasingly difficult to forecast traffic patterns. To capture the traffic variations, we introduce a flexible model where traffic belongs to a polytope. We assume that the traffic demands between nodes can be carried on many paths, with respect to network resources. Moreover, to guarantee the network stability and to make the routing easy to implement, the proportions of traffic flowing through each path have to be independent of the current traffic demands. We show that a minimum-cost routing satisfying the previous properties can be efficiently computed by column and constraint generations. We then present several strategies related to certain algorithmic details. Finally, theoretical and computational studies show that this new flexible model can be much more economical than a classical deterministic model based on a given traffic matrix. This paper can be considered as a mathematical framework for a new flexible virtual private network service offer. It also introduces a new concept: the routing of a polytope.This work was done in part while the authors were working at France Telecom Research and Development, Issy-les-Moulineaux, France.     

QoS-Aware and Resource-Efficient Dynamic Slicing Mechanism for Internet of Things

With the popularization of terminal devices and services in Internet of things (IoT), it will be a challenge to design a network resource allocation method meeting various QoS requirements and effectively using substrate resources. In this paper, a dynamic network slicing mechanism including virtual network (VN) mapping and VN reconfiguration is proposed to provide network slices for services. Firstly, a service priority model is defined to create queue for resource allocation. Then a slice including Virtual Network Function (VNF) placement and routing with optimal cost is generated by VN mapping. Next, considering temporal variations of service resource requirements, the size of network slice is adjusted dynamically to guarantee resource utilization in VN reconfiguration. Additionally, load balancing factors are designed to make traffic balanced. Simulation results show that dynamic slicing mechanism not only saves 22% and 31% cost than static slicing mechanism with extending shortest path (SS_ESP) and dynamic slicing mechanism with embedding single path (DS_ESP), but also maintains high service acceptance rate.     

Q-Learning Based Routing Protocol for Congestion Avoidance

The end-to-end delay in a wired network is strongly dependent on congestion on intermediate nodes. Among lots of feasible approaches to avoid congestion efficiently, congestion-aware routing protocols tend to search for an uncongested path toward the destination through rule-based approaches in reactive/incident-driven and distributed methods. However, these previous approaches have a problem accommodating the changing network environments in autonomous and self-adaptive operations dynamically. To overcome this drawback, we present a new congestion-aware routing protocol based on a Q-learning algorithm in software-defined networks where logically centralized network operation enables intelligent control and management of network resources. In a proposed routing protocol, either one of uncongested neighboring nodes are randomly selected as next hop to distribute traffic load to multiple paths or Q-learning algorithm is applied to decide the next hop by modeling the state, Q-value, and reward function to set the desired path toward the destination. A new reward function that consists of a buffer occupancy, link reliability and hop count is considered. Moreover, look ahead algorithm is employed to update the Q-value with values within two hops simultaneously. This approach leads to a decision of the optimal next hop by taking congestion status in two hops into account, accordingly. Finally, the simulation results presented approximately 20% higher packet delivery ratio and 15% shorter end-to-end delay, compared to those with the existing scheme by avoiding congestion adaptively.     

一种新型的动态路由和波长分配综合算法

讨论了WDM光网中，在动态业务流量和有限范围波长变换情况下的动态路由和波长分配问题。基于Moone-Dijkstra算法，考虑到动态波长变换的可能和限制，提出了一种新型的、可实现动态最小代价路由和最佳虚波长通道的综合启发式算法(DMC-OVWP)。该算法对路由子问题和波长分配子问题既相互独立，又相互结合，优化了RWA。以中国教育和科研计算机网(CERNET)为拓扑背景，基于本算法进行了计算机仿真，并对实验结果进行了比较分析，证明本算法可充分利用网络信息获取较低的阻塞率。     

一种基于多播路由图的最小子树图搜索算法

提出了一种基于网络编码的新的多播路由算法,该算法在搜索信源节点到各接收者路径族的过程中,考虑了不同路径族之间链路的共享,以降低带宽资源消耗,提高网络性能.基于得到的多播路由图,提出了一种最小子树图搜索算法,并利用最小子树图的性质,对相应于多播路由图的子树图进行化简.最后,在最小子树图上进行有效的网络编码,所有的网络编码问题可以简化为搜索多播网络的最小子树图问题.     

A neural algorithm for finding the shortest flow path for an automated guided vehicle system

The automated guided vehicle (AGV)system is emerging as the dominant technology to maximize the flexibility of material handling, while increasing the overall productivity of manufacturing operations. This paper presents a new way of finding the shortest flow path for an AGV system on a specific routing structure. An optimal solution of the system is determined by using an approach based on the Hopfield neural network with the simulated annealing (SA) procedure. In other words, the proposed approach reduces the total cost of an AGV delivery path from one workstation to another on the shop floor. By changing the temperature of the two-stage SA, a solution can be found that avoids potential collisions between AGVs. Both the flow path and the potential collision, which are major problems in AGV systems, may be solved simultaneously by the proposed neural network approach. Other advantages offered by the proposed method are its simplicity compared with operations research (OR)methods and a decreased number of needed AGVs. The performance of the approach is also investigated.