通信工程網(wǎng)絡(luò)技術(shù)外文翻譯文獻(xiàn)翻譯外文文獻(xiàn)

1、. 外文翻譯譯文題目：在WDM代理網(wǎng)絡(luò)中基于蟻群的動(dòng)態(tài)路由和波長(zhǎng)分配原稿題目：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代理網(wǎng)絡(luò)中基于蟻群的動(dòng)態(tài)路由和波長(zhǎng)分配【摘要】在這篇論文中，我們提出一種在波長(zhǎng)連續(xù)性約束波分復(fù)用（WDM）光網(wǎng)絡(luò)中基于蟻群算法的動(dòng)態(tài)路由與波長(zhǎng)分配。通過(guò)采用一個(gè)新的路由表結(jié)構(gòu)和保持大量的螞蟻在網(wǎng)絡(luò)中合作探

2、索網(wǎng)絡(luò)狀態(tài)和不斷更新路由表的方式，我們新的蟻群算法能夠有效地支持蟻群覓食任務(wù)的路由選擇波分復(fù)用（WDM）網(wǎng)絡(luò)中波長(zhǎng)分配，并允許一個(gè)連接設(shè)置迅速到達(dá)小的設(shè)置時(shí)間。大量基于ns-2網(wǎng)絡(luò)仿真結(jié)果模擬表明，該算法能夠很好得適應(yīng)流量變化和達(dá)到一個(gè)比起固定路由算法較低的阻塞概率?！娟P(guān)鍵詞】路由，波長(zhǎng)分配，算法，WDM（波分復(fù)用），蟻群算法1. 介紹所有采用波分復(fù)用（WDM）光網(wǎng)絡(luò)都有一個(gè)巨大的帶寬容量，他們顯示成為下一代互聯(lián)網(wǎng)骨干。在所有光網(wǎng)絡(luò)中，數(shù)據(jù)路由在光學(xué)通道被叫做光路。路由和波長(zhǎng)分配（RWA）問(wèn)題是如何為一個(gè)連接請(qǐng)求確定路由和波長(zhǎng)。沒有了波長(zhǎng)轉(zhuǎn)換功能，一個(gè)光路必須在所有鏈接中使用相同的波長(zhǎng)，這被稱

3、為波長(zhǎng)連續(xù)性限制。路由和波長(zhǎng)分配(RWA)問(wèn)題通常被歸類為靜態(tài)和動(dòng)態(tài)兩種。在靜態(tài)路由和波長(zhǎng)分配問(wèn)題中，連接請(qǐng)問(wèn)是預(yù)先給出的，問(wèn)題就變成如何為所有請(qǐng)求建立光路，使得總數(shù)量的波長(zhǎng)被最小化。靜態(tài)路由和波長(zhǎng)分配問(wèn)題已經(jīng)被證明是一個(gè)NP完全問(wèn)題。在動(dòng)態(tài)路由和波長(zhǎng)分配問(wèn)題中，流量是動(dòng)態(tài)的以及連接請(qǐng)求到達(dá)的隨機(jī)性使得它變得更為困難。啟發(fā)式算法通常被用來(lái)解決這個(gè)問(wèn)題。一般來(lái)說(shuō)，一個(gè)動(dòng)態(tài)的路由和波長(zhǎng)分配算法的目的是使在整個(gè)網(wǎng)絡(luò)中總阻塞概率最小化。在我們的工作中，我們關(guān)注波長(zhǎng)連續(xù)性約束的動(dòng)態(tài)RWA問(wèn)題。在著作中，動(dòng)態(tài)RWA問(wèn)題通常被分為兩種子問(wèn)題，分別可以解決：路由和波長(zhǎng)分配。路由方案可以分為固定路由，固定備用路

4、由和自適應(yīng)路由。在固定的路由方案，有一個(gè)專門為源和目的的路線。每當(dāng)一個(gè)請(qǐng)求出現(xiàn)在這一對(duì)源和目的中，這條路線就會(huì)試圖對(duì)波長(zhǎng)進(jìn)行分配。固定路由簡(jiǎn)單，但是通常導(dǎo)致高阻塞概率。固定備用路由方法具備更好的性能在多路徑節(jié)點(diǎn)對(duì)方面。在自適應(yīng)路由方案中，當(dāng)一個(gè)連接請(qǐng)求到來(lái)時(shí)，路線的計(jì)算是基于當(dāng)前網(wǎng)絡(luò)狀況，從而得到最好的性能。然而，自適應(yīng)路由需要很高的復(fù)雜計(jì)算。一個(gè)更詳細(xì)的路由調(diào)查和波長(zhǎng)分配可以在2中找到。自適應(yīng)RWA方案在論文中總是需要來(lái)自于控制協(xié)議的特殊支持以獲得全球網(wǎng)絡(luò)狀態(tài)。此外，啟發(fā)式算法在一個(gè)請(qǐng)求到達(dá)之后執(zhí)行路由和波長(zhǎng)搜索任務(wù)必須權(quán)衡復(fù)雜度和性能。這也造成高設(shè)置延遲和控制開銷。一個(gè)可能的方法來(lái)克服這些

5、問(wèn)題是使用基于蟻群的移動(dòng)代理3?；谙伻旱拇砺酚煞椒ɡ^承了移動(dòng)代理行為和蟻群系統(tǒng)的優(yōu)勢(shì)。最近的結(jié)果表明，這種方法可以在電路控制的控制和分組交換網(wǎng)絡(luò)中產(chǎn)生高效的性能。在本文中，我們主要研究一個(gè)新的基于蟻群代理算法為波分復(fù)用網(wǎng)絡(luò)的動(dòng)態(tài)RWA問(wèn)題在波長(zhǎng)連續(xù)性約束之下。我們的研究旨在通過(guò)使用適當(dāng)數(shù)量的螞蟻來(lái)減少阻塞概率和路徑設(shè)置時(shí)間，蟻群在連接請(qǐng)求帶來(lái)之前持續(xù)執(zhí)行路徑搜索任務(wù)，這樣的路由選擇和波長(zhǎng)分配請(qǐng)求的執(zhí)行是簡(jiǎn)單地查找路由表。為了實(shí)現(xiàn)這一目標(biāo)，為我們新的算法開發(fā)一個(gè)新的路由表結(jié)構(gòu)，一個(gè)蟻群控制方案和一個(gè)信息素更新機(jī)制。本文余下部分組織如下：在第二節(jié)，我們討論相關(guān)工作。第三節(jié)，在波長(zhǎng)連續(xù)性約束之下

6、的波分復(fù)用網(wǎng)絡(luò)的中我們?yōu)閯?dòng)態(tài)RWA問(wèn)題提出新的方法。第四節(jié)，描述我們初步仿真和分析結(jié)果。最后，我們的結(jié)論和未來(lái)的工作在第五節(jié)進(jìn)行了討論。2. 相關(guān)工作最近的研究結(jié)果表明，通信網(wǎng)絡(luò)中的路由可以通過(guò)蟻群優(yōu)化（ACO）3方法有效地解決。路由解決方案建立在基于蟻群在代理網(wǎng)絡(luò)狀態(tài)中的覓食行為。這些集體代理通過(guò)環(huán)境中信息素拖拽（stigmergy）間接溝通。通過(guò)下面的的另一個(gè)信息素軌跡，一個(gè)代理可以找到一個(gè)“好”的路線，這條路線最短，從源到目的地路由數(shù)據(jù)最不擁擠。兩種基本算法是由Schoonderwoerd et al.4提出的對(duì)電話網(wǎng)絡(luò)的基于蟻群控制（ABC）和由Di Caro et al.5提出的基于

7、蟻群的分組交換網(wǎng)絡(luò)。有一些后續(xù)的提高路由性能的改進(jìn)方案，包括使用動(dòng)態(tài)編程9的智能代理，增強(qiáng)蟻群對(duì)環(huán)境適應(yīng)能力10的強(qiáng)化學(xué)習(xí)以及適應(yīng)蟻群搜索過(guò)程控制參數(shù)11的遺傳算法。而以上的研究主要集中在電子通信網(wǎng)絡(luò)中的路由問(wèn)題，我們?cè)诒疚闹械呐d趣是波長(zhǎng)連續(xù)性約束下的波分復(fù)用光網(wǎng)絡(luò)的動(dòng)態(tài)RWA問(wèn)題。Valera et al.12提出了一種蟻群算法來(lái)解決靜態(tài)RWA問(wèn)題。目標(biāo)在于使一個(gè)給定網(wǎng)絡(luò)拓?fù)浜土髁烤仃嚨牟ㄩL(zhǎng)要求數(shù)量盡量減少。波長(zhǎng)分配僅僅使用一個(gè)貪婪的方法，它為每個(gè)鏈接指定最低可用波長(zhǎng)。一個(gè)螞蟻的路由選擇是基于每個(gè)連接的吸引力。每只螞蟻都有自己的可以被其他螞蟻拒絕的信息素。每只螞蟻都留有一個(gè)用于路線回溯和循環(huán)

8、回避的之前訪問(wèn)節(jié)點(diǎn)的“禁忌”列表。信息素的更新可以使用不同的方法。該方法最好的結(jié)果是吸引螞蟻的路徑數(shù)量隨著穿越的螞蟻數(shù)量越來(lái)越多而獲得全球更新。這個(gè)結(jié)果可以相比于Nagasu 啟發(fā)式13，但是他需要更長(zhǎng)的計(jì)算時(shí)間。然后，這個(gè)方法不能直接應(yīng)用于動(dòng)態(tài)RWA問(wèn)題。Garlick et al.14提出了一種基于蟻群的算法來(lái)解決動(dòng)態(tài)RWA問(wèn)題。當(dāng)一個(gè)新的連接請(qǐng)求到來(lái)時(shí)，大量的螞蟻從源出發(fā)到目的地。螞蟻評(píng)估一條路徑是基于其長(zhǎng)度和這條路徑的平均可用波長(zhǎng)。當(dāng)一只螞蟻到達(dá)目的地，全球信息素更新被執(zhí)行。信息素更新的需求依據(jù)：一旦一個(gè)連接被建立，網(wǎng)絡(luò)信息素矩陣重置。為一個(gè)連接請(qǐng)求的最后最好路徑的產(chǎn)生是當(dāng)所有的螞蟻完

9、成他們的探索任務(wù)。作者表明，該算法在所有可用波長(zhǎng)中探求最短路徑15比一個(gè)詳盡的探索具有更高的性能。作為一個(gè)新組螞蟻必須為新的連接請(qǐng)求啟動(dòng)，設(shè)置延時(shí)會(huì)由于大型網(wǎng)絡(luò)等待螞蟻而變得非常高。事實(shí)上，這種方法不會(huì)顯示來(lái)自于不同請(qǐng)求的螞蟻的集體行為，這是基于蟻群系統(tǒng)的一個(gè)重要方面。3. 基于蟻群的RWA算法 一個(gè)光學(xué)波分復(fù)用(WDM)網(wǎng)絡(luò)可以表示為由N個(gè)節(jié)點(diǎn)和E 鏈接的圖。我們假設(shè)每個(gè)鏈接是雙向容量的W波段和節(jié)點(diǎn)沒有波長(zhǎng)轉(zhuǎn)換能力(波長(zhǎng)連續(xù)性限制)。為了支持螞蟻路由選擇,每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)有一個(gè)路由表和N-1條目。在一個(gè)i和ki相鄰的節(jié)點(diǎn)，路由表有一個(gè)ki序列。每個(gè)條目對(duì)應(yīng)到目的節(jié)點(diǎn),每一列對(duì)應(yīng)一個(gè)相鄰節(jié)點(diǎn)。當(dāng)一

10、只螞蟻向目的節(jié)點(diǎn)d運(yùn)動(dòng)時(shí)，這個(gè)值用作鄰居節(jié)點(diǎn)n的選擇概率。為了支持波長(zhǎng)分配,我們引入了選擇概率的每個(gè)波長(zhǎng)到路由表。對(duì)于每個(gè)相鄰的節(jié)點(diǎn),讓概率是一只螞蟻選擇波長(zhǎng)j，當(dāng)它移動(dòng)到目的地d。 圖1所示的是當(dāng)W=1的一個(gè)新的路由表的新的例子。當(dāng)一個(gè)連接請(qǐng)求發(fā)生在源節(jié)點(diǎn)1和目的節(jié)點(diǎn)6，節(jié)點(diǎn)3將被選擇作為下一跳,因?yàn)?lt; 。在這種情況下，因?yàn)镻1 < P2，波長(zhǎng)2是優(yōu)于波長(zhǎng)1。 Fig. 1. A network and its routing table from node 1在一個(gè)節(jié)點(diǎn)上,螞蟻是由一個(gè)給定的概率隨機(jī)選擇到目的地，每T個(gè)時(shí)間單位。這里和T是設(shè)計(jì)參數(shù)。一只螞蟻被認(rèn)為是一個(gè)移動(dòng)代理:

11、它負(fù)責(zé)在其旅行路線上收集信息,執(zhí)行路由表更新訪問(wèn)節(jié)點(diǎn),并繼續(xù)前進(jìn)見圖2。 Ant launched Update pheromone Ant killed Fig. 2. Ants moving and updating tasks一只螞蟻從源移動(dòng)到目的地,在一Fig. 2. Ants moving and updating tasks個(gè)選定的波長(zhǎng)上一個(gè)節(jié)點(diǎn)到一個(gè)節(jié)點(diǎn)運(yùn)動(dòng)。它的下一站是隨機(jī)決定的：一個(gè)相鄰點(diǎn)的選擇概率是基于路由表的。當(dāng)一只螞蟻到達(dá)目的地節(jié)點(diǎn)或當(dāng)它不能選擇一個(gè)空閑的波長(zhǎng)選擇的路徑為其下一步行動(dòng)時(shí)將被剔除。為了避免“凍結(jié)”狀態(tài)，所有螞蟻專注于一個(gè)路線(停滯)，隨機(jī)方案介紹：每個(gè)螞蟻

12、選擇下一跳的隨機(jī)與利用概率。當(dāng)一個(gè)連接請(qǐng)求到達(dá)時(shí)，路徑將決定基于最高的選擇概率相鄰節(jié)點(diǎn)的條目。波長(zhǎng)分配是基于路由表的波長(zhǎng)選擇概率,或其他一些傳統(tǒng)可以使用的啟發(fā)式方法。當(dāng)一只螞蟻訪問(wèn)一個(gè)節(jié)點(diǎn),它以其旅行過(guò)程中收集的信息來(lái)更新路由表的元素。信息素更新的原理描述如下：假設(shè)一只螞蟻從源移動(dòng)到目標(biāo)d后的s路徑(s,i-1,i,d)。當(dāng)螞蟻到達(dá)節(jié)點(diǎn)i，它將對(duì)應(yīng)節(jié)點(diǎn)s更新條目。當(dāng)其它相鄰節(jié)點(diǎn)概率減少時(shí)，相鄰i-1節(jié)點(diǎn)概率也減少。對(duì)于最近一次訪問(wèn)的相鄰i-1節(jié)點(diǎn)，相應(yīng)的空閑波長(zhǎng)概率增加了，然而波長(zhǎng)對(duì)應(yīng)的概率繁忙程度降低了。更為正式的是，假設(shè)在時(shí)間t，螞蟻訪問(wèn)節(jié)點(diǎn)i，所以在下次t + 1路由條目是由下面的公式?jīng)Q

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 Scho

14、ol of Computer 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 struc

15、ture and keeping 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 se

16、tup promptly 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 tha

17、t adopt wavelength-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

18、to determine 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 RW

19、A problem and 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.

20、In the dynamic 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

21、work, we focus 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

22、 routing and 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 pro

23、bability. The 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, adapt

24、ive routing 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 t

25、hat perform 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

26、 ant-based 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 an

27、t-based agent 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

28、 arrival so 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 res

29、t of this paper 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 fu

30、ture works 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. T

31、hese collective 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 al

32、gorithms are 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

33、 dynamic programming 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 r

34、outing problem 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 waveleng

35、th requirement 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

36、 by others. 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 numbe

37、r of traversed 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.

38、 When a new 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

39、on a per-demand 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 availa

40、ble wavelengths 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, wh

41、ich is an important 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

42、constraint). 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 s

43、election probability 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 wavele

44、ngth j when 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

45、 case. Fig. 1. A network 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

46、table updating on visited 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 neig

47、hbor is selected based 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 r

48、andom scheme is introduced: 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

49、 probabilities from the 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 t

50、o destination d following 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 correspon

51、ding to free wavelengths 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 probabiliti

52、es for all neighbors 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

53、affect all the entries 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

54、W bits corresponding 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 in

55、formation) can be found 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 increa

56、sed pheromone is proportional 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 networkSel

57、ect a random destination;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 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 wavele