Improved offline multi-objective routing and wavelength assignment in optical networks

Abstract

Optical networks act as a backbone for coming generation high speed applications. These applications demand a very high bandwidth which can be exploited with the use of wavelength division multiplexing (WDM) technology. The issue of setting light paths for the traffic demands is routing and wavelength assignment (RWA) problem. Based on the type of traffic patterns, it can be categorized as offline or online RWA. In this paper, an effective solution to offline (static) routing and wavelength assignment is presented considering multiple objectives simultaneously. Initially, the flower pollination (FP) technique is utilized. Then the problem is extended with the parallel hybrid technique with flower pollination and intelligent water drop algorithm (FPIWDA). Further, FPIWD is hybrid in parallel with simulated annealing (SA) algorithm to propose a parallel hybrid algorithm FPIWDSA. The results obtained through extensive simulation show the superiority of FPIWD as compared to FP. Moreover, the results in terms of blocking probability with respect to wavelengths and load of FPIWDSA are more propitious than FP and FPIWD.

Keywords

offline / online / flower pollination (FP) / intelligent water drop (IWD) / simulated annealing (SA) / blocking probability / static / robustness / flexibility / heuristic / wavelength division multiplexing (WDM)

1 1 Introduction

Laser speckle contrast imaging (LSCI) is a powerful and easy-to-use method for blood flow mapping, especially in semi-transparent tissues. For this reason, this technique was first used to visualize retinal blood flow [1]. Although LSCI can be used for tissues possessing high scattering properties such as skin, the most impressive results are achieved with tissues having weak scattering properties. To date, LSCI has been actively used in cerebral blood flow (CBF) mapping [2–4] and intraoperative control in neurosurgery [5]. Laser Doppler flowmetry (LDF) is physically similar to LSCI [6] and essentially used for spatially-integrated blood flow measurements. Although modifications of scanning LDF are known, their temporal and spatial resolutions are limited by the scanning system capability [7]. Compared with LDF, LSCI can provide non-scanning full-field imaging of a relatively wide area of an object with a passable resolution.

Monitoring of skin perfusion is important for diagnosis and therapy of some diseases. For instance, Huang et al. [8] proposed LSCI as a tool to estimate efficiency of laser treatment for nevus flammeus. Moreover, LSCI is also applied to visualize retinal blood flow [1,9]. In these applications, Tamaki et al. [9] developed the algorithm they called “normalized blur”, in this method, ratio of the mean speckle intensity to difference between the mean speckle intensity and the instant speckle intensity is calculated. Another application of LSCI in the retina is for the study of retinal blood flow changes under functional activation using pharmacological agents [10].

LSCI was introduced initially as noninvasive method for CBF imaging; however, this technique requires optical clear [11] of a skin tissue and a part of the skull is removed to attain a direct access to the cortex [2,12]. LSCI is often combined with other methods such as multispectral reflectance imaging [13], fluorescence imaging of nicotinamide adenine dinucleotide in its reduced form (NADH) and flavoproteins [7], or used independently [14].

Another possible implementation of LSCI is to study depolarization wave propagation in the cortex [15], which is the main mechanism of migraine headache. In these studies, LDF was adopted for quantitative measurements of blood flow in a specific location of the cortex and LSCI was used for spatial mapping of the changes of CBF induced by the propagation of depolarization wave [7].

LDF has been the most common tool for CBF measurements with essentially point-wise access. Although magnetic resonance imaging and positron emission tomography can be also used to perform such monitoring, disadvantages of these techniques include low spatial resolution, contrast agents usage, ionizing radiation, and high cost of service [16]. By comparison, LSCI is a low-cost and high-performance imaging technique [17]. However, quantitative measurements using LSCI is very complicated and still need improvements, particularly with regard to multiple scattering [4,18,19], sensitivity to light polarization [7,20], and velocity distribution of the particles [21,22]. To solve these problems partially, calibration on tissue phantom with known parameters [23] or multi-exposure LSCI [24] can be used. In spite of these efforts, LSCI is most widely used for relative measurements [2–4,7], rather than quantitative studies.

The estimated optical resolution of our LSCI system is approximately 120 µm, and typical size of cerebral blood vessels varies in the range from 5 to 500 µm. Obviously, optical resolution of this imaging system is not high enough to distinguish most of the vessels in microcirculatory bed. Although a single capillary, arteriole, or venule cannot be resolved in a speckle image, extracting information on microcirculatory bed is possible through analysis of contrast distribution within the portion of the speckle image that corresponds to unresolved images of these small vessels [4,25].

The common method for retrieving information from a speckle contrast image is based on region of interest (ROI) analysis. A few ROIs are usually selected in a speckle contrast image. Typically, one ROI is set to represent the vein of macrocirculation and another ROI represents the microcirculatory network [4,25]. Further processing is performed usually to calculate the average contrast value over the entire ROI. Much of the information on blood flow within the analyzed region is unused because of such averaging. Instead of adopting the ROI method, we proposed a simple technique to retain this additional information using histogram analysis of speckle contrast distribution. We attempted to enhance the capabilities of LSCI to perform qualitative measurements by describing a simple algorithm based on histogram analysis of an image obtain by LSCI to provide rapid differentiation of macro- and microcirculation.

2 2 Speckle image analysis

Typical speckle contrast image of a rat cortex is shown in Fig. 1. This image is obtained with the following setup: He–Ne laser working at 632.8 nm was used to illuminate the rat cortex; complementary metal-oxide-semiconductor (CMOS)-camera Basler acA2500-14 gm with 2.2 µm × 2.2 µm pixel size was adopted for image acquisition; imaging lens Computar M1614-MP2 is at f/6; speckle/pixel size ratio is approximately 9; spatial speckle contrast distribution was calculated using 7×7 pixels sliding window; 50 consecutive frames of raw speckle image were averaged into the single speckle contrast image; and frame rate of initial raw data is equal to 40 frames per second.

Fig.1 Typical speckle contrast image

Full size|PPT slide

In this work, spatial speckle contrast distribution was calculated using the standard equation:

(1) $K={\displaystyle \frac{\sigma }{\langle I\rangle }},$

where $\langle I\rangle$ is the mean value and $\sigma$ is the standard deviation of intensity in the analyzed region of the raw speckle image. To reduce processing time, parallel computing and digital image processing were implemented [26]. Using these approaches, spatial speckle contrast analysis is described. Spatial distribution of the mean intensity $\langle I\rangle$ is given as convolution of the raw speckle image $IRaw$ with the $N\times N$ kernel matrix $K$ of ones [27].

(2) $\langle I\rangle ={\displaystyle \frac{\mathrm{1}}{N^{\mathrm{2}}}}\left(IRaw*K\right).$

Array of the standard deviation $\sigma$ can also be expressed as [27]

(3) $\sigma ={\displaystyle \frac{\sqrt{{\displaystyle \frac{\mathrm{1}}{N^{\mathrm{2}}-\mathrm{1}}}\left[IRa{w}^{\mathrm{2}}\ast K-{\displaystyle \frac{{\left(IRaw\ast K\right)}^{\mathrm{2}}}{N^{\mathrm{2}}}}\right]}}{{\displaystyle \frac{IRaw\ast K}{N^{\mathrm{2}}}}}}.$

In that case, the resulting speckle contrast map can be effectively calculated by vectorization of Eq. (1).

Further processing is devoted to differentiation of blood flow between macro- and microlevels. In this work, we employed histogram analysis of the speckle contrast image [26] to achieve rapid integral multiscale analysis of blood flow. We selected three ROIs in the speckle contrast image, as depicted in Fig. 2. Each ROI represents a vascular bed with different scale. The first ROI (ROI1) contains both large and small vessels. As shown in the speckle contrast map, the distributions of blood flow in these both vessels are different. Results from the histogram analysis of laser speckle contrast image of this ROI showed two patterns of blood flow distribution, which were attributed to large (left side mode) and small (right side mode) vessels, respectively (see the purple curve in Fig. 2(b)). To validate this assumption, we constructed two additional small-sized ROIs: the second one (ROI2) corresponds to small optically unresolved vessels and the third ROI (ROI3) was a region with large vessels (as shown in Fig. 2(a)). The respective histograms of ROI2 and ROI3 coincide well with that of the ROI1 (Fig. 2(b)). A combination of histograms of the small-sized ROIs gives an expected bimodal distribution. In addition, the histogram of ROI1 contains some additional side modes corresponding to relatively large resolvable vessels on each side of the main trunk.

Thus, histogram analysis can provide integral rating of the speckle contrast image as a whole. However, information on some vessels can be lost and implicated because of unreasonably large ROIs.

Fig.2 Histogram analysis of speckle image. (a) Multiple ROIs in speckle contrast image; (b) normalized histograms of these ROIs

Full size|PPT slide

During the experiment, changes of these modes with time can be tracked, including their relative and absolute positions, shape, and magnitude. According to the proposed concept, relative changes of these modes provide information on rearrangement of blood flow between macro- and microcirculatory network.

The main steps of the algorithm are as follows:

1) Constructing ROI that covers large vessels and adjacent microvascular bed;

2) Calculating histogram of this ROI;

3) Retrieving the modes of distribution and their parameters.

In the case of time lapse measurements of laser speckle contrast image, some artifacts can be caused by the motion of the sample. As a result of this sample motion, the pre-selected ROI (green block in Fig. 3) is not always in a desirable position. To resolve this issue, we improved the algorithm using correlation-based motion tracker. We selected a ROI to track and calculate cross-correlation of each speckle contrast image in time series with this region, as depicted in Fig. 4. Then, a peak value in each spatial cross-correlation function was found, and the position of this peak defines new coordinates of the ROI according to current image. Finally, a new ROI within each frame of the time series was constructed with respect to their own new coordinates (purple block in Fig. 3). Moreover, the selected region must have a well-recognizable structure (large vessels or network of small vessels) for cross-correlation procedure.

Fig.3 Two consecutive frames of the time lapse measurements. Green block denotes statically overlaid ROI, whereas purple block is defined by correlation-based motion tracker

Full size|PPT slide

Fig.4 Cross-correlations between selection and the next frame in series. Purple block shows new ROI coordinates with respect to maximum of cross-correlation function; green block is a statically overlaid ROI

Full size|PPT slide

Results of time lapse measurements performed with statically overlaid ROI and with correlation-based motion tracker are presented in Fig. 5. The motion tracker can compensate the most part of artificial movements, and by using this tracker, the problem of exiting the vessels out of ROI can be avoided.

Fig.5 Results of time lapse measurements performed with statically overlaid ROI (a) and with correlation based motion tracker (b)

Full size|PPT slide

3 3 Experiment with animals

We mapped changes of CBF in hypertensive rats for differentiation of macro- and microcirculation. Hypertension is a key factor that leads to ischemic stroke development [28,29]. In 1959, Lassen proposed a concept for the retention of CBF even if arterial blood pressure dramatically changes from 60 to 150 mmHg [30]. However, changes in arterial pressure by even 10 mmHg are accompanied by the changes in CBF of 2%–7% [31]. Until now, research on the effects of changes of arterial pressure on CBF is insufficient. Hence, we performed a series of experiments with normotensive rats (n =10) and hypertensive (n =10) rats by phenylephrine. Phenylephrine is known to be unavailable over the blood-brain barrier [32], and thus we can measure the changes in CBF induced by the changes in blood pressure only. Arterial hypertension was provoked using the method described in Ref. [33]. According to this method, rats were kept in isolation or overpopulation for four months. Then, all rats were anesthetized using isoflurane, and craniotomy was performed using dental drill (Mikroton, Aesculap) with constant saline irrigation to prevent tissue overheating. CBF in rat cortex was measured at 30 min after surgery. Blood pressure monitoring was applied using pressure catheters (PE-50 with a PE-10 tip, Scientific Commodities Inc., Lake Havasu City, Arizona, USA) introduced into the femoral artery and the PowerLab data acquisition device.

Phenylephrine was injected at three time points to raise the peripheral blood pressure (PBP). Results of this study showed that phenylephrine injection leads to dose-dependent increase of blood pressure in normotensive rats from (105±5) mmHg to (171±7) mmHg (from (142±9) mmHg to (195±11) mmHg in hypertensive rats). The rate of change of blood pressure in normotensive rats (64%) was greater than that (37%) in hypertensive rats (Fig. 6(a)). This result can be explained by higher basal blood pressure level in hypertensive individuals.

Changes in CBF under rapidly increasing PBP were detected in hypertensive rats only. The typical dynamics of CBF in normotensive and hypertensive rats are shown in Figs. 6(b) and 6(c).

Fig.6 Typical example of changes of mean arterial pressure (a) and CBF after bolus injection of phenylephrine in three doses (0.25, 0.5, and 1 µg/kg) in normotensive (b) and hypertensive (c) rats

Full size|PPT slide

As shown in Fig. 6, an increase in CBF at microcirculatory level in response to sharp rise in peripheral arterial pressure is typical for hypertensive rats, rather than normotensive rats. CBF remains constant in normotensive rats, independent of significant hypertensive response to phenylephrine. In contrast to normotensive rats, in hypertensive individuals, peripheral pressure response to the third phenylephrine injection is accompanied by weak increase in microcirculatory and appreciable decrease in CBF in sagittal sinus. The possible mechanism underlying these processes is the decrease in venous blood flow, i.e., reallocation of CBF to the area where the blood–tissue oxygen exchange occurs, apparently, to prevent hypoxia. The method proposed for differentiation of blood flow at macro- and microlevels allows multi-scaled analysis of CBF at spasmodic changes in arterial pressure on the basis of chronic hypertension. Such kind of analysis is important particularly for further studies on hemorrhagic and ischemic stroke development provoked by hypertension.

4 4 Discussion and conclusion

The practical application of the proposed algorithm to study CBF in living animals shows that histogram analysis of an image obtained by LSCI may potentially improve the qualitative measurements of conventional LSCI. However, the advantages of this method over the other techniques should be verified to improve method efficiency. A possible approach to implement is a detailed analysis of the contrast distribution involving calculations of skewness, kurtosis, and higher moments, which characterize the shape of the contrast distribution. The contrast distribution can be considered as a rough approximation to velocity distribution in the ROI. Such approximation seems to be inappropriate for quantitative estimation, but is still acceptable for comparative qualitative analysis. As such, kurtosis and dispersion properties of the velocity distribution can be used as a diagnostic variable as well as the most probable value used in this study. Asymmetry of the distribution (skewness) requires more complicated analysis. This property can be referred to sensitivity of experimental setup with specified settings (e.g., exposure time, f-number, and uniformity of illumination). In this case, averaging the contrast value over the entire ROI can provide inaccurate result that is biased to the stretched, asymmetric side tail of the contrast distribution. The possible resolution to this problem is analyzing the skewness of the contrast distribution for a sample with known parameters and considering the results of analysis in the subsequent measurements. We believe that the analysis of these properties may provide some additional information on micro- and macrocirculations and their temporal dynamics.

Animal study demonstrated that acute hypertensive responses induced by bolus injection of phenylephrine in three different doses have no effect on CBF in normotensive individuals. In hypertensive rats, the third injection of phenylephrine led to an increase in macrocirculation and a decrease in microcirculation of CBF as response to dramatically increased PBP. Thus, the differentiation between macro- and microcirculations under functional activation allows for physiological analysis of the hemodynamic mechanisms underlying pathological changes in CBF, which in turn can help in developing new methods for pharmacological correction of macro- and microcirculation in the brain under different physiological conditions.

References

[1] Murthy C S R, Gurusamy M. WDM Optical Networks: concepts, Design, and Algorithms, Singapore: Prentice-hall, 2002, 1–15

[2] Berthold J, Saleh A A M, Blair L, Simmons J M. Optical networking: past, present, and future. Journal of Lightwave Technology, 2008, 26(9): 1104–1118

[3] Gavanelli M, Nonato M, Peano A, Bertozzi D. Logic programming approaches for routing fault-free and maximally parallel wavelength-routed optical networks on chip. Theory and Practice of Logic Programming, 2017, 17(5–6): 800–818

[4] Singh S. Performance comparison of optical network topologies in the presence of optimized semiconductor optical amplifiers. Journal of Optical Communications and Networking, 2009, 1(4): 313–323

[5] Kaur G, Singh M L. Effect of four-wave mixing in WDM optical fibre systems. Optik, 2009, 120(6): 268–273

[6] Lin H C, Wang S H, Tsai C P. Traffic intensity based fixed alternate routing in all optical WDM networks. In: Proceedings of IEEE ICC’06. Istanbul: IEEE, 2006, 2439–2446

[7] Zang H, Jue J P, Mukherjee B. A review of routing and wavelength assignment approaches for wavelength routed optical WDM network. Optical Networks Magazine, 2000, 1: 47–60

[8] Chlamtac I, Ganz A, Karmi G. Light path communications: an approach to high bandwidth optical WAN’s. IEEE Transactions on Communications, 1992, 40(7): 1171–1182

[9] Zang H, Jue J P, Sahasrabuddhe L, Ramamurthy R, Mukherjee B. Dynamic Light path establishment in wavelength routed WDM network. IEEE Communications Magazine, 2001, 39(9): 100–108

[10] Bala K, Stern T E, Bala K. Algorithms for routing in a linear light wave network. In: Proceedings of IEEE Infocom’91. Bal Harbour: IEEE, 1991, 1–9

[11] Wason A, Kaler R S. Generic routing and wavelength assignment algorithm for a wavelength-routed WDM Network. Optik (Stuttgart), 2011, 122(12): 1100–1106

[12] Chap T, Wang X, Xu S, Tanaka Y. Link-disjoint routing algorithms with link-disjoint degree and resource utilization concern in translucent WDM optical networks. In: Proceedings of IEEE ICACT’2011. Seoul: IEEE, 2011, 357–362

[13] Guo L, Wang X, Ji W, Hou W, Wu T, Jin F. A new waveband switching routing algorithm in WDM optical networks. In: Proceedings of IEEE ICACT’08. Gangwon-Do: IEEE, 2008, 2151–2154

[14] Ebrahimzadeh A, Rahbar A G, Alizadeh B. Binary quadratic programming formulation for routing and wavelength assignment problem in all-optical WDM networks. Optical Switching and Networking, 2013, 10(4): 354–365

[15] Christodoulopoulos K, Manousakis K, Varvarigos E. Offline routing and wavelength assignment in transparent WDM networks. IEEE/ACM Transactions on Networking, 2010, 18(5): 1557–1570

[16] Leesutthipornchai P, Charnsripinyo C, Wattanapongsakorn N. Solving multi-objective routing and wavelength assignment in WDM network using hybrid evolutionary computation approach. Computer Communications, 2010, 33(18): 2246–2259

[17] Crichigno J, Xie C, Shu W, Wu M Y, Ghani N A. Multiobjective approach for throughput optimization and traffic engineering in WDM networks. In: Proceedings of IEEE Forty-Third Asilomar Conference on Signals, Systems and Computers. Pacific Grove: IEEE, 2009, 1043–1047

[18] Singh Suk, Singh Sur. A hybrid WDM ring–tree topology delivering efficient utilization of bandwidth over resilient infrastructure. Photonic Network Communications, 2018, 35(3): 325–334

[19] Bisbal D, Miguel I, González F, Blas J, Aguado J C, Fernández P, Durán J, Durán R, Lorenzo R M, Abril E J, López M. Dynamic routing and wavelength assignment in optical networks by means of genetic algorithms. Journal of Photonic Network Communication, 2004, 7(1): 43–58

[20] Ramesh T K, Lakshmi N A, Madhu A, Ready K S, Vaya P R. A proactive and self-regulated ant based RWA protocol for all optical WDM networks. In: Proceedings of IEEE International Conference on Process Automation Control and Computing. Coimbatore: IEEE, 2011, 1–5

[21] Chen M T, Lin B M T, Tseng S S. Ant colony optimization for dynamic routing and wavelength Assignment in WDM networks with sparse wavelength conversion. Journal of Engineering Applications of Artificial Intelligence, 2011, 24(2): 295–305

[22] Triay J, Cervello-Pastor C. An ant based algorithm for distributed routing and wavelength assignment in dynamic optical networks. IEEE Journal on Selected Areas in Communications, 2010, 28(4): 542–552

[23] Ngo S H, Jiang X, Horiguchi S. An ant based approach for dynamic RWA in optical WDM networks. Journal of Photonic Network Communications, 2006, 11(1): 39–48

[24] Aragon V M, Miguel R J, Merayo N, Agerado J C, Fernadez P, Lorenzo R M, Abril E A. New algorithm for the distributed RWA problem in WDM networks using ant colony optimization. In: Tomkos I, Neri F, Solé Pareta J, Masip Bruin X, Sánchez Lopez S, eds. Optical Network Design and Modeling. Berlin: Springer Heidelberg, 2007, 299–308

[25] Kavian Y S, Rashedi A, Mahani A, Ghassemlooy Z. Routing and wavelength assignment in optical networks using artificial bee colony algorithm. Optik, 2013, 124(12): 1243–1249

[26] Hassan A, Phillips C. Chaotic particle swarm optimization for dynamic routing and wavelength assignment in all optical WDM networks. In: Proceedings of IEEE International Conference on Signal Processing and Communication System. Omaha: IEEE, 2009

[27] Lezama F, Castañón G, Sarmiento A M. Routing and wavelength assignment in all optical networks using differential evolution optimization. Photonic Network Communications, 2013, 26(2–3): 103–119

[28] Bayraktar Z, Komurcu M, Bossard J A, Werner D H. The wind-driven optimization technique and its application in electromagnetics. IEEE Transactions on Antennas and Propagation, 2013, 61(5): 2745–2757

[29] Yang X S. Flower pollination algorithm for global optimization. In: Durand-Lose J, Jonoska N, eds. Unconventional Computation and Natural Computation. Berlin: Springer Heidelberg, 2012, 240–249

[30] Kirkpatrick S, Gelatt C D Jr, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220(4598): 671–680

[31] Hosseini H S. The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. International Journal of Bio-inspired Computation, 2009, 1(1/2): 71–79

[32] Wason A, Kaler R S. Wavelength assignment problem in optical WDM networks. International Journal of Computer Science and Network Security, 2007, 7(4): 27–31

[33] Balasubramani K, Marcus K A. Study on flower pollination algorithm and its applications. International Journal of Application or Innovation in Engineering & Management, 2014, 3(11): 230–235

[34] Tyagi D K, Chaubey V K, Khandelwal P. Routing and wavelength assignment in WDM network using IWD based algorithm. In: Proceedings of IEEE International Conference on Computing, Communication, and Automation (ICCCA). Noida: IEEE, 2016

[35] Hosseini H S. Problem solving by intelligent water drops. In: IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007, 3226–3231

[36] Yadav A K, Singh A, Azeem A, Rahi O P. Application of simulated annealing and genetic algorithm in engineering application. International Journal of Advances in Engineering and Technology, 2011, 1(2): 81–85

[37] Fang Z, Gu X, Chen J. Improved heuristic flower pollination algorithm for solving multi-dimensional knapsack problems. In: Proceedings of IEEE international conference on Intelligent Computation Technology and Automation. Changsha: IEEE, 2017, 33–38

[38] Abdel-Baset M, Hezam I. hybrid flower pollination algorithm for engineering optimization problems. International Journal of Computers and Applications, 2016, 140(12): 10–23

[39] Selvarani S, Sadhasivam G. An intelligent water drop algorithm for optimizing task scheduling in grid environment. International Arab Journal of Information Technology, 2016, 13(6): 627–634

[40] Askarzadeh A, Coelho L D S, Klein C E, Mariani V C. A population based simulated annealing algorithm for global optimization. In: Proceedings of IEEE International Conference on Systems, Man and Cybernetics(SMC). Budapest: IEEE, 2016, 004626–004633

[41] Mantawy A H, Abdel-Magid Y L, Selim S Z. A simulated annealing algorithm for unit commitment. IEEE Transactions on Power Systems, 1998, 13(1): 197–204

Acknowledgements

Harpreet Kaur would like to thank Dean RIC, I.K. Gujral Punjab Technical University Jalandhar, Kapurthala for making required resources available throughout the completion of this research work.

RIGHTS & PERMISSIONS

2019 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature