《通信工程 网络技术 外文翻译 文献翻译 外文文献》由会员分享，可在线阅读，更多相关《通信工程 网络技术 外文翻译 文献翻译 外文文献（15页珍藏版）》请在金锄头文库上搜索。
1、 外文翻译译文题目：在WDM代理网络中基于蚁群的动态路由和波长分配原稿题目：Dynamic Routing and Wavelength Assignment in WDM Net- works with Ant-Based Agents原稿出处：Embedded and Ubiquitous Compter science Volume 3207.2004.pp 829-838 在WDM代理网络中基于蚁群的动态路由和波长分配【摘要】在这篇论文中，我们提出一种在波长连续性约束波分复用（WDM）光网络中基于蚁群算法的动态路由与波长分配。通过采用一个新的路由表结构和保持大量的蚂蚁在网络中合作探索网
2、络状态和不断更新路由表的方式，我们新的蚁群算法能够有效地支持蚁群觅食任务的路由选择波分复用（WDM）网络中波长分配，并允许一个连接设置迅速到达小的设置时间。大量基于ns-2网络仿真结果模拟表明，该算法能够很好得适应流量变化和达到一个比起固定路由算法较低的阻塞概率。【关键词】路由，波长分配，算法，WDM（波分复用），蚁群算法1. 介绍所有采用波分复用（WDM）光网络都有一个巨大的带宽容量，他们显示成为下一代互联网骨干。在所有光网络中，数据路由在光学通道被叫做光路。路由和波长分配（RWA）问题是如何为一个连接请求确定路由和波长。没有了波长转换功能，一个光路必须在所有链接中使用相同的波长，这被称为波
3、长连续性限制。路由和波长分配(RWA)问题通常被归类为静态和动态两种。在静态路由和波长分配问题中，连接请问是预先给出的，问题就变成如何为所有请求建立光路，使得总数量的波长被最小化。静态路由和波长分配问题已经被证明是一个NP完全问题。在动态路由和波长分配问题中，流量是动态的以及连接请求到达的随机性使得它变得更为困难。启发式算法通常被用来解决这个问题。一般来说，一个动态的路由和波长分配算法的目的是使在整个网络中总阻塞概率最小化。在我们的工作中，我们关注波长连续性约束的动态RWA问题。在著作中，动态RWA问题通常被分为两种子问题，分别可以解决：路由和波长分配。路由方案可以分为固定路由，固定备用路由和
4、自适应路由。在固定的路由方案，有一个专门为源和目的的路线。每当一个请求出现在这一对源和目的中，这条路线就会试图对波长进行分配。固定路由简单，但是通常导致高阻塞概率。固定备用路由方法具备更好的性能在多路径节点对方面。在自适应路由方案中，当一个连接请求到来时，路线的计算是基于当前网络状况，从而得到最好的性能。然而，自适应路由需要很高的复杂计算。一个更详细的路由调查和波长分配可以在2中找到。自适应RWA方案在论文中总是需要来自于控制协议的特殊支持以获得全球网络状态。此外，启发式算法在一个请求到达之后执行路由和波长搜索任务必须权衡复杂度和性能。这也造成高设置延迟和控制开销。一个可能的方法来克服这些问题
5、是使用基于蚁群的移动代理3。基于蚁群的代理路由方法继承了移动代理行为和蚁群系统的优势。最近的结果表明，这种方法可以在电路控制的控制和分组交换网络中产生高效的性能。在本文中，我们主要研究一个新的基于蚁群代理算法为波分复用网络的动态RWA问题在波长连续性约束之下。我们的研究旨在通过使用适当数量的蚂蚁来减少阻塞概率和路径设置时间，蚁群在连接请求带来之前持续执行路径搜索任务，这样的路由选择和波长分配请求的执行是简单地查找路由表。为了实现这一目标，为我们新的算法开发一个新的路由表结构，一个蚁群控制方案和一个信息素更新机制。本文余下部分组织如下：在第二节，我们讨论相关工作。第三节，在波长连续性约束之下的波
6、分复用网络的中我们为动态RWA问题提出新的方法。第四节，描述我们初步仿真和分析结果。最后，我们的结论和未来的工作在第五节进行了讨论。2. 相关工作最近的研究结果表明，通信网络中的路由可以通过蚁群优化（ACO）3方法有效地解决。路由解决方案建立在基于蚁群在代理网络状态中的觅食行为。这些集体代理通过环境中信息素拖拽（stigmergy）间接沟通。通过下面的的另一个信息素轨迹，一个代理可以找到一个“好”的路线，这条路线最短，从源到目的地路由数据最不拥挤。两种基本算法是由Schoonderwoerd et al.4提出的对电话网络的基于蚁群控制（ABC）和由Di Caro et al.5提出的基于蚁群
7、的分组交换网络。有一些后续的提高路由性能的改进方案，包括使用动态编程9的智能代理，增强蚁群对环境适应能力10的强化学习以及适应蚁群搜索过程控制参数11的遗传算法。而以上的研究主要集中在电子通信网络中的路由问题，我们在本文中的兴趣是波长连续性约束下的波分复用光网络的动态RWA问题。Valera et al.12提出了一种蚁群算法来解决静态RWA问题。目标在于使一个给定网络拓扑和流量矩阵的波长要求数量尽量减少。波长分配仅仅使用一个贪婪的方法，它为每个链接指定最低可用波长。一个蚂蚁的路由选择是基于每个连接的吸引力。每只蚂蚁都有自己的可以被其他蚂蚁拒绝的信息素。每只蚂蚁都留有一个用于路线回溯和循环回避
8、的之前访问节点的“禁忌”列表。信息素的更新可以使用不同的方法。该方法最好的结果是吸引蚂蚁的路径数量随着穿越的蚂蚁数量越来越多而获得全球更新。这个结果可以相比于Nagasu 启发式13，但是他需要更长的计算时间。然后，这个方法不能直接应用于动态RWA问题。Garlick et al.14提出了一种基于蚁群的算法来解决动态RWA问题。当一个新的连接请求到来时，大量的蚂蚁从源出发到目的地。蚂蚁评估一条路径是基于其长度和这条路径的平均可用波长。当一只蚂蚁到达目的地，全球信息素更新被执行。信息素更新的需求依据：一旦一个连接被建立，网络信息素矩阵重置。为一个连接请求的最后最好路径的产生是当所有的蚂蚁完成他
9、们的探索任务。作者表明，该算法在所有可用波长中探求最短路径15比一个详尽的探索具有更高的性能。作为一个新组蚂蚁必须为新的连接请求启动，设置延时会由于大型网络等待蚂蚁而变得非常高。事实上，这种方法不会显示来自于不同请求的蚂蚁的集体行为，这是基于蚁群系统的一个重要方面。3. 基于蚁群的RWA算法 一个光学波分复用(WDM)网络可以表示为由N个节点和E 链接的图。我们假设每个链接是双向容量的W波段和节点没有波长转换能力(波长连续性限制)。为了支持蚂蚁路由选择,每个网络节点有一个路由表和N-1条目。在一个i和ki相邻的节点，路由表有一个ki序列。每个条目对应到目的节点,每一列对应一个相邻节点。当一只蚂
10、蚁向目的节点d运动时，这个值用作邻居节点n的选择概率。为了支持波长分配,我们引入了选择概率的每个波长到路由表。对于每个相邻的节点,让概率是一只蚂蚁选择波长j，当它移动到目的地d。 图1所示的是当W=1的一个新的路由表的新的例子。当一个连接请求发生在源节点1和目的节点6，节点3将被选择作为下一跳,因为 。在这种情况下，因为P1 P2，波长2是优于波长1。 Fig. 1. A network and its routing table from node 1在一个节点上,蚂蚁是由一个给定的概率随机选择到目的地，每T个时间单位。这里和T是设计参数。一只蚂蚁被认为是一个移动代理:它负责在其旅行路线上收
11、集信息,执行路由表更新访问节点,并继续前进见图2。 Ant launched Update pheromone Ant killed Fig. 2. Ants moving and updating tasks一只蚂蚁从源移动到目的地,在一Fig. 2. Ants moving and updating tasks个选定的波长上一个节点到一个节点运动。它的下一站是随机决定的：一个相邻点的选择概率是基于路由表的。当一只蚂蚁到达目的地节点或当它不能选择一个空闲的波长选择的路径为其下一步行动时将被剔除。为了避免“冻结”状态，所有蚂蚁专注于一个路线(停滞)，随机方案介绍：每个蚂蚁选择下一跳的随机与利用
12、概率。当一个连接请求到达时，路径将决定基于最高的选择概率相邻节点的条目。波长分配是基于路由表的波长选择概率,或其他一些传统可以使用的启发式方法。当一只蚂蚁访问一个节点,它以其旅行过程中收集的信息来更新路由表的元素。信息素更新的原理描述如下：假设一只蚂蚁从源移动到目标d后的s路径(s,i-1,i,d)。当蚂蚁到达节点i，它将对应节点s更新条目。当其它相邻节点概率减少时，相邻i-1节点概率也减少。对于最近一次访问的相邻i-1节点，相应的空闲波长概率增加了，然而波长对应的概率繁忙程度降低了。更为正式的是，假设在时间t，蚂蚁访问节点i，所以在下次t + 1路由条目是由下面的公式决定的(记住,所有的相邻
13、总概率总和是1): （1） （2） Dynamic Routing and Wavelength Assignment in WDMNetworks with Ant-Based AgentsSon-Hong Ngo, Xiaohong Jiang, Susumu Horiguchi, and Minyi Guo Graduate School of Information Science, Japan Advanced Institute of Science andTechnology, Japansonhong,jiang,horijaist.ac.jp2 School of Compu
14、ter Science and Engineering, The University of Aizu, Japanminyiu-aizu.ac.jpAbstractIn this paper, we propose an ant-based algorithm for dynamic routing and wavelength assignment (RWA) in WDM optical networks under the wavelength continuity constraint. By adopting a new routing table structure and ke
15、eping a number of ants in the network to cooperatively explore the network states and continuously update the routing tables, our new ant algorithm can efficiently support the ants foraging tasks of route selection and wavelength assignment in WDM networks, and allow a connection to be setup promptl
16、y onarrival with a small setup time. Extensive simulation results based on the ns-2 network simulator indicate that the proposed algorithm can adapt well to traffic variations and achieves a lower blocking probability than the fixed routing algorithm.1 IntroductionAll optical networks that adopt wav
17、elength-division-multiplexing (WDM) technology have a huge bandwidth capacity, and they show promise as the backbone of the next generation Internet. In all optical networks, data are routed in optical channels called lightpaths. The Routing and Wavelength Assignment (RWA) problem is how to determin
18、e both a route and wavelengths for a connection request. Without wavelength conversion capability, a lightpath must use the same wavelength on all the links along its route, which is referred to as the wavelength continuity constraint.The RWA problem is usually classified as the static RWA problem a
19、nd the dynamic RWA problem. In the static RWA problem, the connection requests are given in advance, and the problem becomes how to establish lightpaths for all these requests so that the total number of wavelengths is minimized. Static RWA has been proved to be an NP-complete problem 1. In the dyna
20、mic RWA problem, the traffic is dynamic with connection requests arriving randomly, making it more difficult. Heuristic algorithms are usually employed to resolve this problem. Generally, a dynamic RWA algorithm aims to minimize the total blocking probability in the entire network。In our work, we fo
21、cus on the dynamic RWA problem with wavelength continuity constraint. In the literature, the dynamic RWA problem is usually divided into two sub-problems that can be solved separately: routing and wavelength assignment. Routing schemes can be classified into fixed routing, fixed-alternate routing an
22、d adaptive routing. In the fixed routing scheme, one route is dedicated for a sourcedestinationpair. Whenever a request occurs between this source-destination pair, this route is attempted for wavelength assignment. The fixed routing method is simple but usually causes a high blocking probability. T
23、he fixed-alternate routing method has better performance with multiple paths dedicated for a node pair. In the adaptive routing scheme, the route is computed at the time the connection request arrives, based on the current network state, thus it yields the best performance. However, adaptive routing
24、 requires high computational complexity. A more detailed survey of routing and wavelength assignment can be found in 2。The adaptive RWA solutions in the literature always need special support from control protocol to obtain the global state of the network. Moreover, heuristic algorithms that perform
25、 route and wavelength searching tasks after a request arrives must take into account the tradeoff between complexity and performance. This also contributes to high setup delay and control overhead. A possible approach to overcome these problems is the use of ant-based mobile agents 3. The ant-based
26、agent routing approach inherits advantages from both mobile agents behaviors and an ant colony system. Recent results show that this approach could yield efficient performance in the control of both circuit switching 4 and packet switching networks 5。In this paper, we investigate a new ant-based age
27、nt algorithm for the dynamic RWA problem in WDM networks under the constraint of wavelength continuity. Our study aims to reduce both blocking probability and path setup time by using a suitable amount of ants, which continuously perform path searching tasks before the connection requests arrival so
28、 that the route selection and wavelength assignment of a request are performed by simply looking up the routing tables. To achieve that goal, we develop a new routing table structure, a scheme for ant population control and a mechanism for pheromone updating, for our new algorithm。The rest of this p
29、aper is organized as follows: In section 2, we discuss related works. Section 3 presents our new approach to the dynamic RWA problem in WDM networks under wavelength continuity constraint. Section 4 describes our preliminary simulation and analysis results. Finally, our conclusions and future works
30、are discussed in Section 52 Related WorkRecent research results show that the routing in communication networks can be resolved efficiently by means of Ant Colony Optimization (ACO) 3. The routing solution can be built using ant-based agents behavior in their foraging of network states. These collec
31、tive agents indirectly communicate through pheromone trailing (stigmergy) in the environment. By following the pheromone trail of another, an agent can find a “good” route in terms of shortest, least congested path from the source to the destination to route the network data. Two basic algorithms ar
32、e ant-based control (ABC) for telephone networks, which was proposed by Schoonderwoerd et al. 4 and AntNet for packet switching networks, which was proposed by Di Caro et al. 5. Some subsequent enhancement schemes to improve the ant-based routing performance include smart agents which use dynamic pr
33、ogramming 9, reinforcement learning which enhances the ants adaptability to its environment 10, and a genetic algorithm which adapts the ant control parameters to the search process 11. While the Dynamic Routing and Wavelength Assignment in WDM Networks 831 above research focuses on the routing prob
34、lem in electronic communication networks, our interest in this paper is the dynamic RWA problem in WDM optical networks with the constraint of wavelength continuity.Valera et al. 12 proposed an ACO approach for solving the static RWA problem. The goal is to minimize the number of wavelength requirem
35、ent given a network topology and a traffic matrix. The wavelength assignment simply uses a greedy method that assigns the lowest available wavelength to each link. An ants route is selected based on the weight of attraction of each link. Each ant has its own pheromone that can be repulsed by others.
36、 Each ant keeps a “tabu” list of previously visited node for route backtracking and loop avoidance. The pheromone updating can use different methods; the best result of this approach is obtained through global update when the weight of attraction of ant for a path increases with the number of traver
37、sed ants. The result can be compared to the conventional Nagatsu heuristic 13, but it requires a much longer computational time. However, this approach cannot be applied directly to the dynamic RWA problem.Garlick et al. 14 proposed an ACO-based algorithm to solve the dynamic RWA problem. When a new
38、 connection request arrives, a number of ants are launched from the source to the destination. Ants evaluate a path based on its length and the mean available wavelengths along the path. Global pheromone updating is performed when an ant reaches its destination. The pheromone updating is on a per-de
39、mand basis: the network pheromone matrix is reset once a connection is established. The final best path for a connection request is made when all ants complete their exploitation tasks. The authors showed that this algorithm has better performance than an exhaustive search over all available wavelen
40、gths for the shortest path 15. As a new set of ants must be launched for each new connection request, the setup delay will be very high due to the waiting for ants in large networks. In fact, this approach does not show the collective behavior of ants that come from different requests, which is an i
41、mportant aspect of ant-based systems。3 Ant-Based RWA AlgorithmAn optical WDM network is represented by a graph with N nodes and E links. We assume that each link is bi-directional with a capacity of W wavelengths and no nodes have a wavelength conversion capability (wavelength continuity constraint)
42、. In order to support the route selection by ants, each network node has a routing table with N1 entry. In a node i with ki neighbors, the routing table has a ki column. Each entry corresponds to a destination node and each column corresponds to a neighbor node. The value is used as the selection pr
43、obability of neighbor node n when an ant is moving towards its destination node d. In order to support the wavelength assignment, we introduce the selection probability of each wavelength into the routing table. For each neighbor node, let be the probability that an ant selects the wavelength j when
44、 it moves to destination d.An example of the new routing table when W=2 is shown in Fig.1. When a connection request occurs between source node 1 and destination node 6, node 3 will be selected as next hop because Wavelength 2 is preferred over wavelength 1 because P1 P2 in that case. Fig. 1. A netw
45、ork and its routing table from node 1On a node, ants are launched with a given probability to a randomly selected destination every T time units. Here and T are design parameters. Each ant is considered to be a mobile agent: it collects information on its trip, performs routing table updating on vis
46、ited nodes, and continues to move forward as illustrated in Fig.2. Ant launched Update pheromone Ant killed Fig. 2. Ants moving and updating tasksAn ant moves from a source to a destination, node by node on a selected wavelength. Its next hop is determined stochastically: a neighbor is selected base
47、d on its selecting probabilities in the routing table. An ant is killed when it reaches its destination node or when it cannot select a free wavelength on the selected path for its next move. To avoid a “frozen” status in which all ants concentrate on one route (stagnation), a random scheme is intro
48、duced: each ant selects its next hop randomly with an exploiting probability (). When a connection request arrives, the path will be determined based on the highest selection probability node among neighbors entries. The wavelength assignment is based on the wavelength selection probabilities from t
49、he routing table, or some others conventional heuristics can be used。Whenever an ant visits a node, it updates the routing table element with the information gathered during its trip. The principle of pheromone update is described as follows. Suppose an ant moves from source s to destination d follo
50、wing the path (s, i-1, i,d).When the ant arrives at node i, it will update the entry corresponding to the node s: the probability of neighbor i-1 is increased while the probabilities of others neighbors is decreased. For the last visited neighbor i-1, the probabilities corresponding to free waveleng
51、ths are increased, whereas the probabilities corresponding to busy wavelengths are decreased.More formally, suppose that at time t, an ant visits node i, so the values for routing entry in next time t+1 are determined by the following formula(remember that the sum of probabilities for all neighbors
52、is always 1): （1） （2）As described in a previous work 9, smart agents can efficiently in improve the performance of ant-based routing systems. Based on the idea of smart agents, the pheromone updating will affect not only the entry corresponding to the source node, but also will affect all the entrie
53、s corresponding to previous nodes along the path. In order to facility smart updating, an ant must push the information about visited nodes into its stack: node identification, a binary mask that determines the status of free wavelengths on the links it traversed (this mask has W bits corresponding
54、to the number of wavelengths). This stack also serves for loop detection and backtracking, to ensure that ants will not move forever on the network。The reason for using a wavelength mask is that under wavelength continuity constraint, the number of free wavelengths (congested information) can be fou
55、nd exactly along a path; this will enhance the performance of the ACO approach. At each node, the wavelength mask is updated as below： （3）Eqs.6 and 7 guarantee that (the normalization condition for wavelength selection probability), and they also ensure that the amount of increased pheromone is prop
56、ortional to the number of free wavelengths. For the wavelength assignment, we use a simple heuristic: the wavelength with the highest probability among the free wavelengths will be selected。Our algorithm is briefly described as follows:Ant generationDoFor each node in networkSelect a random destinat
57、ion;Launch ants to this destination with a probabilityEnd forIncrease time by a time-step for ants generationUntil (end of simulation)Ant foragingFor each ant from source s to destination d do (in parallel)While current node i dUpdate routing table elementsPush trips state into stackIf (found a next
58、 hop)Move to next hopElseKill antEnd ifEnd whileEnd forRouting and Wavelength SelectionFor each connection request do (in parallel)Select a path with highest probabilitySearch a free wavelength with highest probabilityIf (found)Setup a lightpathElseConsider a blocking caseEnd ifEnd for4 Simulation R
59、esults and AnalysisAn extensive experimental study based on Network Simulator ns-2 16 has been performed to validate our new ant-based algorithm for RWA. As the original ns-2 supports packet switching, this feature was used to simulate the ants moves. We suppose that the control plane for optical WD
60、M networks is implemented in an electronic netDynamic Routing and Wavelength Assignment in WDM Networks 835 work that has a same topology as the optical network. An optical routing module was added into ns-2 to simulate our RWA algorithm。We used the fixed routing scheme with shortest path algorithm
61、for performance comparison. All the tests were conducted based on the NSF network topology with 14 nodes and 21 links as shown in Fig.3, and W=8 and W=16 were considered in our experiments。5 Conclusion and Future WorksIn this paper, we have proposed an ant-based mobile agents approach to solving the
62、 routing and wavelength assignment problems in dynamic WDM networks. We developed a new routing table structure and also a way to adapt the routing table according to network state, using a suitable number of ants that continuously exploit the network. Our simulation shows that the new ant-based alg
63、orithm outperforms the fixedrouting algorithm using shortest path and First Fit wavelength assignment scheme. An advantage of this new algorithm is that the path for a connection request is determined。Comparisons between new Ant-based algorithm and Fixed routing algorithm. (a) Comparison results whe
64、n W = 8. (b) Comparison results when W = 16。Immediately on arrival, based on the adapting routing table, so the setup delay time is significantly reduced compared to the fixed routing scheme. Our new algorithm is very flexible in the sense that the number of ants in the network can be efficiently co
65、ntrolled by simply adjust the launching probability of ants to achieve the best performance。In our future work, we will extend this algorithm by using a reinforcement learning approach such that others ACO control parameters could be automatically adjusted for a given network condition. The other he
66、uristics for routing and wavelength assignment with wavelength conversion will also be investigated。Acknowledgement. This research is partly supported by the Grand-In-Aid of scientific research (B) 14380138 and 16700056, Japan Science Promotion Society。References1. Ramaswami, R., Sivarajan, K.N.: Ro
67、uting and wavelength assignment in all-optical networks.IEEE/ACM Transactions on Networking, vol. 3 (1995) 489-500.2. Zang H. et al.: A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks. Optical Networks Magazine, vol. 1, no. 1 (2000) 47-60.3. Bonabeau
68、, E. et al.: Swarm intelligence: from natural to artificial systems. Oxford University Press, Inc., New York (1999)4. Schoonderwoerd, R. et al.: Ant-like agents for load balancing in telecommunications networks.Proc. of the First International Conference on Autonomous Agents. ACM Press,(1997) 209-21
69、6.5. Di Caro, G., Dorigo, M.: AntNet: A mobile agents approach to adaptive routing. Technical Report 97-12, IRIDIA, Universite Libre de Bruxelles (1997)6. Ramamurthy, S., Mukherjee, B.: Fixed-Alternate Routing and Wavelength Conversion in Wavelength Routed Optical Networks. Proc. IEEE Globecom (1998
70、)7. Li, L., Somani, A.K.: Dynamic wavelength routing using congestion and neighborhood information. IEEE/ACM Trans. on Networking, vol. 7, no. 5 (1999) 779-786.8. Kassabalidis, I. et al.: Swarm intelligence for routing in communication networks. Proc. IEEE Globecom (2001)9. Bonabeau, E. et al.: Rout
71、ing in Telecommunication Networks with Smart Ant-Like Agents. Proc. IATA, Lectures Notes in AI, vol. 1437, Springer Verlag (1998)10. Legge, D. Baxendale, P.: An Agent-Managed Ant-Based Network Control System.AAMAS-3 (2003)11. White, T. et al.: ASGA: Improving the Ant System by Integration with Genet
72、ic Algorithms. Proc. GP/SGA (1998)12. Navarro Varela, G., Sinclair, M.C.: Ant Colony Optimization for Virtual-Wavelength-Path Routing and Wavelength Allocation. Proc.CEC99, Washington DC, USA (1999).13. Nagatsu, N. et al.: Number of wavelengths required for constructing large-scale optical path netw
73、orks. Electronics and Comm. in Japan, part 1, vol. 78, no. 9 (1995) 1-11.14. Garlick, R.M., Barr, R.: Dynamic wavelength routing in WDM networks via Ant Colony Optimization. Ant Algorithms, Springer-Verlag Publishing (2002) 250-25515. Mokhtar, A., Azizoglu, M.: Adaptive wavelength routing in all-optical networks. IEEE Trans. on Networking, vol. 6 (1998) 197-206.16. The Network Simulator, ns-2. http:/www.isi.edu/nsnam/ns/index.html (2003)1
