Less Carbon Footprint in Edge Computing by Joint Task Offloading and Energy Sharing

Zhanwei Yu1, Yi Zhao1, Tao Deng2, Lei You3, and Di Yuan1
1Department of Information Technology, Uppsala University, Sweden
2School of Computer Science and Technology, Soochow University, China
3Department of Engineering Technology, Technical University of Denmark, Denmark
1{zhanwei.yu; yi.zhao<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
In sprite the state-of-the-art, significantly reducing carbon footprint (CF) in communications systems remains urgent. We address this challenge in the context of edge computing. The carbon intensity of electricity supply largely varies spatially as well as temporally. This, together with energy sharing via a battery management system (BMS), justifies the potential of CF-oriented task offloading, by redistributing the computational tasks in time and space. In this paper, we consider optimal task scheduling and offloading, as well as battery charging to minimize the total CF. We formulate this CF minimization problem as an integer linear programming model. However, we demonstrate that, via a graph-based reformulation, the problem can be cast as a minimum-cost flow problem. This finding reveals that global optimum can be admitted in polynomial time. Numerical results using real-world data show that optimization can reduce up to $83.3\%$ of the total CF.

carbon footprint, scheduling, edge computing.

§ INTRODUCTION

The current carbon footprint (CF) in information and communications technology (ICT) sector could be as high as $2.1\%$ to $3.9\%$ of the total figure [1]. For Europe, for example, the baseline is $2\%$[2]. The authors of [3] list four potential measures that can significantly help reduce the CF due to ICT, one of which is edge computing.

The edge servers consume substantially less energy than conventional cloud data centers, though they need to be densely deployed. For green edge computing, research has been conducted for better design of networks [4], including dynamic right-sizing, geographical load balancing, and the use of renewable energy. However, most works with respect to green edge computing consider energy consumption or efficiency as the objective function, rather than CF explicitly.

Lower energy consumption contributes to reducing CF, however they are not equivalent. For example, in an edge computing network consisting of uniform servers and task distribution, considering only energy consumption would render task offloading useless (which itself would cost energy). However, as the CF intensity differs by time and space, offloading does help. We show a US domestic carbon intensity (CI) data set and another data set for three counties in Europe in Table <ref> [5]. As we can see, there are large differences between spaces and time. For example, the CI in Oregon is five times higher than that in Washington. Also, The CI in Oregon at 24:00 is 31.7% less than that at 08:00. The variation is due to the difference in the availability of various power sources over time and space. This motivates us to use the spatial and temporal information of CI to reduce CF by optimal task offloading and scheduling.

Two real-world data sets of carbon intensity.

2c2*Region     3cCarbon intensity1

2c     08:00     16:00     24:00

3*90 USA      Washington     110     95      95

Oregon     605     579     413

California     325     292      238

3*90 Europe      Sweden     24     26     25

Germany     375     285     381

Poland     593     573     547

* $^1$Unit: gCO2eq/kWh.

Examining the current literature, we highlight the following contributions. The studies in [6, 7, 8, 9, 10, 11] have addressed CF in edge computing or fog computing. The authors of [6] provide a model that can estimate the CF in distributed data centers. Their results show that the total CF of a set of distributed small data centers is less than that from a big data center with equivalent compute capability. The authors of [7] provide a Lyapunov-based algorithm for a distributed data center to minimize electricity cost subject to CF limit. In [8], the authors consider minimizing the CF for video streaming in fog computing networks. In addition, the studies in [9] and [10] provide application placement methods to minimize the CF in fog computing networks. The authors of [11] examine task scheduling policies to minimize the CF of edge computing networks via the drift-plus-penalty methodology in Lyapunov optimization. Table <ref> lists the features of our paper and the related works in [6, 7, 8, 9, 10, 11]. Note that the works in [6, 7, 8, 9, 10] only consider optimizing either the spatial or temporal dimension instead of joint spatio-temporal optimization.

The difference among our paper and the related works.

Work(s)     [c]  Renewable
energy     [c]  Energy
storage     [c]  Spatio-temporal
optimization    [c]  Energy
sharing     [c]  Task

[6]

[7, 8, 9, 10]

[11]

Our work

To the best of our knowledge, the work in [11] is the closest to ours, yet the differences are significant. The system model in our paper considers battery charging on top of task offloading and scheduling, making our scenario more comprehensive. To be more exact, our paper considers task scheduling and offloading, as well as energy sharing with battery charging to minimize the CF, utilizing temporal and spatial information of CI. The main contributions of this paper are as follows.

* We consider an edge computing network with renewable energy sources and batteries, and model the CF for the resulting scenario. We consider task offloading and scheduling, as well as battery charging with energy sharing, with the objective of CF minimization.

* Due to the discrete nature of task offloadling, the CF minimization problem leads to an integer linear programming (ILP) model. However, we reveal that the problem structure admits a reformulation using minimum-cost flow, implying that its global optimum can be computed in polynomial time. Thus our optimization approach is scalable.

* We use real-world CI data to evaluate the performance. The numerical results show that, by optimal CF-aware task offloading and scheduling along with energy sharing, we can reduce up to $83.3\%$ of the total CF.

§ SYSTEM MODEL AND PROBLEM FORMULATION

every picture/.style=line width=0.75pt

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ][dash pattern=on 4.5pt off 4.5pt] (38.5,155.68) .. controls (38.5,107.91) and (92.62,69.18) .. (159.39,69.18) .. controls (226.15,69.18) and (280.28,107.91) .. (280.28,155.68) .. controls (280.28,203.45) and (226.15,242.18) .. (159.39,242.18) .. controls (92.62,242.18) and (38.5,203.45) .. (38.5,155.68) – cycle ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (155.38,15.32) .. controls (155.38,12.23) and (157.89,9.73) .. (160.97,9.73) .. controls (164.06,9.73) and (166.56,12.23) .. (166.56,15.32) .. controls (166.56,18.41) and (164.06,20.91) .. (160.97,20.91) .. controls (157.89,20.91) and (155.38,18.41) .. (155.38,15.32) – cycle ;

(167.98,15.27) .. controls (167.98,15.26) and (167.99,15.25) .. (168,15.25) – (170.69,15.25) .. controls (170.7,15.25) and (170.71,15.26) .. (170.71,15.27) – (170.71,15.32) .. controls (170.71,15.33) and (170.7,15.34) .. (170.69,15.34) – (168,15.34) .. controls (167.99,15.34) and (167.98,15.33) .. (167.98,15.32) – cycle ;

(152.56,10.42) .. controls (152.57,10.41) and (152.58,10.4) .. (152.59,10.41) – (154.92,11.76) .. controls (154.93,11.76) and (154.93,11.77) .. (154.93,11.78) – (154.9,11.83) .. controls (154.89,11.84) and (154.88,11.84) .. (154.87,11.84) – (152.54,10.49) .. controls (152.53,10.48) and (152.53,10.47) .. (152.53,10.46) – cycle ;

(155.9,6.97) .. controls (155.91,6.96) and (155.92,6.96) .. (155.92,6.97) – (157.27,9.31) .. controls (157.27,9.31) and (157.27,9.32) .. (157.26,9.33) – (157.22,9.36) .. controls (157.21,9.36) and (157.2,9.36) .. (157.19,9.35) – (155.84,7.02) .. controls (155.84,7.01) and (155.84,7) .. (155.85,6.99) – cycle ;

(160.96,5.61) .. controls (160.97,5.61) and (160.97,5.61) .. (160.97,5.62) – (160.97,8.32) .. controls (160.97,8.33) and (160.97,8.34) .. (160.96,8.34) – (160.9,8.34) .. controls (160.89,8.34) and (160.88,8.33) .. (160.88,8.32) – (160.88,5.62) .. controls (160.88,5.61) and (160.89,5.61) .. (160.9,5.61) – cycle ;

(151.26,15.25) .. controls (151.26,15.24) and (151.27,15.23) .. (151.28,15.23) – (153.97,15.23) .. controls (153.98,15.23) and (153.99,15.24) .. (153.99,15.25) – (153.99,15.3) .. controls (153.99,15.31) and (153.98,15.32) .. (153.97,15.32) – (151.28,15.32) .. controls (151.27,15.32) and (151.26,15.31) .. (151.26,15.3) – cycle ;

(164.51,21.23) .. controls (164.52,21.23) and (164.53,21.23) .. (164.54,21.24) – (165.88,23.57) .. controls (165.89,23.58) and (165.89,23.59) .. (165.88,23.6) – (165.83,23.62) .. controls (165.82,23.63) and (165.81,23.63) .. (165.8,23.62) – (164.46,21.28) .. controls (164.45,21.28) and (164.46,21.26) .. (164.46,21.26) – cycle ;

(161.05,22.31) .. controls (161.06,22.31) and (161.06,22.32) .. (161.06,22.33) – (161.06,25.02) .. controls (161.06,25.03) and (161.06,25.04) .. (161.05,25.04) – (160.99,25.04) .. controls (160.98,25.04) and (160.97,25.03) .. (160.97,25.02) – (160.97,22.33) .. controls (160.97,22.32) and (160.98,22.31) .. (160.99,22.31) – cycle ;

(167.1,18.63) .. controls (167.1,18.62) and (167.11,18.61) .. (167.12,18.62) – (169.46,19.97) .. controls (169.46,19.97) and (169.47,19.98) .. (169.46,19.99) – (169.43,20.04) .. controls (169.43,20.05) and (169.42,20.05) .. (169.41,20.05) – (167.08,18.7) .. controls (167.07,18.69) and (167.07,18.68) .. (167.07,18.67) – cycle ;

(165.88,6.96) .. controls (165.89,6.96) and (165.89,6.97) .. (165.88,6.98) – (164.54,9.31) .. controls (164.53,9.32) and (164.52,9.33) .. (164.51,9.32) – (164.46,9.29) .. controls (164.46,9.29) and (164.45,9.28) .. (164.46,9.27) – (165.8,6.94) .. controls (165.81,6.93) and (165.82,6.92) .. (165.83,6.93) – cycle ;

(169.46,10.34) .. controls (169.47,10.35) and (169.46,10.36) .. (169.46,10.37) – (167.12,11.71) .. controls (167.11,11.72) and (167.1,11.72) .. (167.1,11.71) – (167.07,11.66) .. controls (167.07,11.65) and (167.07,11.64) .. (167.08,11.63) – (169.41,10.29) .. controls (169.42,10.28) and (169.43,10.29) .. (169.43,10.29) – cycle ;

(154.93,18.55) .. controls (154.93,18.56) and (154.93,18.57) .. (154.92,18.58) – (152.59,19.92) .. controls (152.58,19.93) and (152.57,19.93) .. (152.56,19.92) – (152.53,19.87) .. controls (152.53,19.86) and (152.53,19.85) .. (152.54,19.84) – (154.87,18.5) .. controls (154.88,18.49) and (154.89,18.5) .. (154.9,18.5) – cycle ;

(157.13,21.22) .. controls (157.14,21.23) and (157.14,21.24) .. (157.13,21.25) – (155.79,23.58) .. controls (155.78,23.59) and (155.77,23.59) .. (155.76,23.59) – (155.72,23.56) .. controls (155.71,23.55) and (155.7,23.54) .. (155.71,23.54) – (157.06,21.2) .. controls (157.06,21.19) and (157.07,21.19) .. (157.08,21.2) – cycle ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (133.8,32.28) – (137.2,15.21) – (160.28,15.21) – (163.68,32.28) – cycle ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (135.05,26.77) – (162.64,26.72) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (136,20.82) – (161.09,20.82) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (152.28,15.7) – (154.51,32.54) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (145.19,15.54) – (143.19,32.66) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ][line width=1.5]  (170.53,64.02) – (170.53,71.12) .. controls (170.53,73.08) and (160.74,74.67) .. (148.67,74.67) .. controls (136.6,74.67) and (126.82,73.08) .. (126.82,71.12) – (126.82,64.02) .. controls (126.82,62.06) and (136.6,60.47) .. (148.67,60.47) .. controls (160.74,60.47) and (170.53,62.06) .. (170.53,64.02) .. controls (170.53,65.98) and (160.74,67.57) .. (148.67,67.57) .. controls (136.6,67.57) and (126.82,65.98) .. (126.82,64.02) ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (147.75,70.72) .. controls (147.75,70.13) and (148.23,69.65) .. (148.82,69.65) .. controls (149.41,69.65) and (149.89,70.13) .. (149.89,70.72) .. controls (149.89,71.31) and (149.41,71.79) .. (148.82,71.79) .. controls (148.23,71.79) and (147.75,71.31) .. (147.75,70.72) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (151.55,70.72) .. controls (151.55,70.13) and (152.02,69.65) .. (152.62,69.65) .. controls (153.21,69.65) and (153.68,70.13) .. (153.68,70.72) .. controls (153.68,71.31) and (153.21,71.79) .. (152.62,71.79) .. controls (152.02,71.79) and (151.55,71.31) .. (151.55,70.72) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (143.96,70.72) .. controls (143.96,70.13) and (144.44,69.65) .. (145.03,69.65) .. controls (145.62,69.65) and (146.1,70.13) .. (146.1,70.72) .. controls (146.1,71.31) and (145.62,71.79) .. (145.03,71.79) .. controls (144.44,71.79) and (143.96,71.31) .. (143.96,70.72) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (136.18,102.97) – (162.32,102.97) – (162.32,115.73) – (136.18,115.73) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (143.64,104.38) – (140.99,104.38) – (140.99,106.25) – (139.12,106.25) – (139.12,108.9) – (140.99,108.9) – (140.99,110.76) – (143.64,110.76) – (143.64,108.9) – (145.51,108.9) – (145.51,106.25) – (143.64,106.25) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (152.74,106.11) – (159.17,106.11) – (159.17,108.98) – (152.74,108.98) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (140.83,99.67) – (144.1,99.67) – (144.1,100.66) – (140.83,100.66) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (154.7,99.67) – (157.96,99.67) – (157.96,100.66) – (154.7,100.66) – cycle ;

(218.62,58) – (220.35,47.43) – (232.35,47.43) – (234.08,58) – cycle ;

(220.35,47.43) – (221.7,38.59) – (231,38.59) – (232.35,47.43) – cycle ;

(221.7,38.59) – (221.7,30.8) – (231,30.8) – (231,38.59) – cycle ;

(221.7,30.8) – (221.7,20.67) – (231,20.67) – (231,30.8) – cycle ;

(220.35,47.43) – (234.08,58) ;

(218.62,58) – (232.35,47.43) ;

(220.35,47.43) – (231,38.59) ;

(232.35,47.43) – (221.7,38.59) ;

(231,38.59) – (221.7,30.8) ;

(221.7,38.59) – (231,30.8) ;

(221.7,30.8) – (231,20.67) ;

(231,30.8) – (221.7,20.67) ;

(231,24.47) – (244.07,30.8) – (231,30.8) – cycle ;

(231,30.8) – (235.28,26.53) ;

(240.62,30.93) – (240.62,33.07) ;

(221.7,24.47) – (208.63,30.8) – (221.7,30.8) – cycle ;

(217.55,26.8) – (221.7,30.8) ;

(212.22,30.93) – (212.22,33.07) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (227.6,108.6) – (227.6,81) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (99.47,23.7) – (133.3,23.7) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (99.47,23.7) – (99.47,109) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (99.47,109) – (131.3,109) ;
[shift=(133.3,109), rotate = 180] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (148.86,100.97) – (148.86,89.26) ;
[shift=(148.86,87.26), rotate = 90] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (148.67,46.26) – (148.67,57.97) ;
[shift=(148.67,59.97), rotate = 270] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (210.5,67.26) – (175.07,67.26) ;
[shift=(173.07,67.26), rotate = 360] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (227.6,108.6) – (168.8,108.6) ;
[shift=(166.8,108.6), rotate = 360] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (92.32,250.59) .. controls (92.32,247.5) and (94.82,245) .. (97.91,245) .. controls (100.99,245) and (103.5,247.5) .. (103.5,250.59) .. controls (103.5,253.68) and (100.99,256.18) .. (97.91,256.18) .. controls (94.82,256.18) and (92.32,253.68) .. (92.32,250.59) – cycle ;

(104.91,250.53) .. controls (104.91,250.52) and (104.92,250.52) .. (104.93,250.52) – (107.62,250.52) .. controls (107.63,250.52) and (107.64,250.52) .. (107.64,250.53) – (107.64,250.59) .. controls (107.64,250.6) and (107.63,250.61) .. (107.62,250.61) – (104.93,250.61) .. controls (104.92,250.61) and (104.91,250.6) .. (104.91,250.59) – cycle ;

(89.5,245.68) .. controls (89.5,245.67) and (89.51,245.67) .. (89.52,245.68) – (91.85,247.02) .. controls (91.86,247.03) and (91.86,247.04) .. (91.86,247.05) – (91.83,247.1) .. controls (91.83,247.1) and (91.82,247.11) .. (91.81,247.1) – (89.47,245.75) .. controls (89.47,245.75) and (89.46,245.74) .. (89.47,245.73) – cycle ;

(92.83,242.23) .. controls (92.84,242.23) and (92.85,242.23) .. (92.86,242.24) – (94.2,244.57) .. controls (94.21,244.58) and (94.2,244.59) .. (94.2,244.6) – (94.15,244.62) .. controls (94.14,244.63) and (94.13,244.63) .. (94.12,244.62) – (92.78,242.28) .. controls (92.77,242.28) and (92.78,242.26) .. (92.78,242.26) – cycle ;

(97.89,240.87) .. controls (97.9,240.87) and (97.91,240.88) .. (97.91,240.89) – (97.91,243.58) .. controls (97.91,243.59) and (97.9,243.6) .. (97.89,243.6) – (97.83,243.6) .. controls (97.82,243.6) and (97.82,243.59) .. (97.82,243.58) – (97.82,240.89) .. controls (97.82,240.88) and (97.82,240.87) .. (97.83,240.87) – cycle ;

(88.19,250.52) .. controls (88.19,250.51) and (88.2,250.5) .. (88.21,250.5) – (90.9,250.5) .. controls (90.91,250.5) and (90.92,250.51) .. (90.92,250.52) – (90.92,250.57) .. controls (90.92,250.58) and (90.91,250.59) .. (90.9,250.59) – (88.21,250.59) .. controls (88.2,250.59) and (88.19,250.58) .. (88.19,250.57) – cycle ;

(101.44,256.5) .. controls (101.45,256.49) and (101.46,256.5) .. (101.47,256.51) – (102.82,258.84) .. controls (102.82,258.85) and (102.82,258.86) .. (102.81,258.86) – (102.76,258.89) .. controls (102.75,258.9) and (102.74,258.89) .. (102.74,258.88) – (101.39,256.55) .. controls (101.39,256.54) and (101.39,256.53) .. (101.4,256.53) – cycle ;

(97.98,257.57) .. controls (97.99,257.57) and (98,257.58) .. (98,257.59) – (98,260.29) .. controls (98,260.3) and (97.99,260.3) .. (97.98,260.3) – (97.92,260.3) .. controls (97.91,260.3) and (97.91,260.3) .. (97.91,260.29) – (97.91,257.59) .. controls (97.91,257.58) and (97.91,257.57) .. (97.92,257.57) – cycle ;

(104.03,253.89) .. controls (104.04,253.88) and (104.05,253.88) .. (104.06,253.89) – (106.39,255.23) .. controls (106.4,255.24) and (106.4,255.25) .. (106.4,255.26) – (106.37,255.31) .. controls (106.36,255.31) and (106.35,255.32) .. (106.34,255.31) – (104.01,253.96) .. controls (104,253.96) and (104,253.95) .. (104,253.94) – cycle ;

(102.81,242.22) .. controls (102.82,242.23) and (102.82,242.24) .. (102.82,242.25) – (101.47,244.58) .. controls (101.46,244.59) and (101.45,244.59) .. (101.44,244.59) – (101.4,244.56) .. controls (101.39,244.56) and (101.39,244.54) .. (101.39,244.54) – (102.74,242.2) .. controls (102.74,242.19) and (102.75,242.19) .. (102.76,242.2) – cycle ;

(106.4,245.61) .. controls (106.4,245.62) and (106.4,245.63) .. (106.39,245.63) – (104.06,246.98) .. controls (104.05,246.98) and (104.04,246.98) .. (104.03,246.97) – (104,246.93) .. controls (104,246.92) and (104,246.91) .. (104.01,246.9) – (106.34,245.55) .. controls (106.35,245.55) and (106.36,245.55) .. (106.37,245.56) – cycle ;

(91.86,253.82) .. controls (91.86,253.83) and (91.86,253.84) .. (91.85,253.84) – (89.52,255.19) .. controls (89.51,255.19) and (89.5,255.19) .. (89.5,255.18) – (89.47,255.14) .. controls (89.46,255.13) and (89.47,255.12) .. (89.47,255.11) – (91.81,253.76) .. controls (91.82,253.76) and (91.83,253.76) .. (91.83,253.77) – cycle ;

(94.06,256.49) .. controls (94.07,256.49) and (94.07,256.51) .. (94.07,256.51) – (92.72,258.85) .. controls (92.72,258.86) and (92.71,258.86) .. (92.7,258.85) – (92.65,258.83) .. controls (92.64,258.82) and (92.64,258.81) .. (92.64,258.8) – (93.99,256.47) .. controls (93.99,256.46) and (94.01,256.46) .. (94.01,256.46) – cycle ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (70.73,267.55) – (74.13,250.48) – (97.21,250.48) – (100.61,267.55) – cycle ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (71.98,262.04) – (99.58,261.99) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (72.94,256.09) – (98.02,256.09) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (89.21,250.97) – (91.45,267.81) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (82.13,250.81) – (80.13,267.93) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ][line width=1.5]  (105.06,221.49) – (105.06,228.59) .. controls (105.06,230.55) and (95.28,232.14) .. (83.21,232.14) .. controls (71.14,232.14) and (61.35,230.55) .. (61.35,228.59) – (61.35,221.49) .. controls (61.35,219.53) and (71.14,217.94) .. (83.21,217.94) .. controls (95.28,217.94) and (105.06,219.53) .. (105.06,221.49) .. controls (105.06,223.45) and (95.28,225.04) .. (83.21,225.04) .. controls (71.14,225.04) and (61.35,223.45) .. (61.35,221.49) ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (82.29,228.19) .. controls (82.29,227.6) and (82.76,227.12) .. (83.36,227.12) .. controls (83.95,227.12) and (84.43,227.6) .. (84.43,228.19) .. controls (84.43,228.78) and (83.95,229.26) .. (83.36,229.26) .. controls (82.76,229.26) and (82.29,228.78) .. (82.29,228.19) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (86.08,228.19) .. controls (86.08,227.6) and (86.56,227.12) .. (87.15,227.12) .. controls (87.74,227.12) and (88.22,227.6) .. (88.22,228.19) .. controls (88.22,228.78) and (87.74,229.26) .. (87.15,229.26) .. controls (86.56,229.26) and (86.08,228.78) .. (86.08,228.19) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (78.49,228.19) .. controls (78.49,227.6) and (78.97,227.12) .. (79.56,227.12) .. controls (80.15,227.12) and (80.63,227.6) .. (80.63,228.19) .. controls (80.63,228.78) and (80.15,229.26) .. (79.56,229.26) .. controls (78.97,229.26) and (78.49,228.78) .. (78.49,228.19) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (71.11,186.04) – (97.25,186.04) – (97.25,198.8) – (71.11,198.8) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (78.57,187.45) – (75.92,187.45) – (75.92,189.32) – (74.06,189.32) – (74.06,191.96) – (75.92,191.96) – (75.92,193.83) – (78.57,193.83) – (78.57,191.96) – (80.44,191.96) – (80.44,189.32) – (78.57,189.32) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (87.67,189.18) – (94.1,189.18) – (94.1,192.05) – (87.67,192.05) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (75.77,182.74) – (79.03,182.74) – (79.03,183.73) – (75.77,183.73) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (89.63,182.74) – (92.9,182.74) – (92.9,183.73) – (89.63,183.73) – cycle ;

(18.18,213.03) – (19.92,202.46) – (31.92,202.46) – (33.65,213.03) – cycle ;

(19.92,202.46) – (21.27,193.62) – (30.57,193.62) – (31.92,202.46) – cycle ;

(21.27,193.62) – (21.27,185.83) – (30.57,185.83) – (30.57,193.62) – cycle ;

(21.27,185.83) – (21.27,175.7) – (30.57,175.7) – (30.57,185.83) – cycle ;

(19.92,202.46) – (33.65,213.03) ;

(18.18,213.03) – (31.92,202.46) ;

(19.92,202.46) – (30.57,193.62) ;

(31.92,202.46) – (21.27,193.62) ;

(30.57,193.62) – (21.27,185.83) ;

(21.27,193.62) – (30.57,185.83) ;

(21.27,185.83) – (30.57,175.7) ;

(30.57,185.83) – (21.27,175.7) ;

(30.57,179.5) – (43.63,185.83) – (30.57,185.83) – cycle ;

(30.57,185.83) – (34.85,181.57) ;

(40.18,185.97) – (40.18,188.1) ;

(21.27,179.5) – (8.2,185.83) – (21.27,185.83) – cycle ;

(17.12,181.83) – (21.27,185.83) ;

(11.78,185.97) – (11.78,188.1) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (127.33,192.67) – (127.33,260.87) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (127.33,260.87) – (105.47,260.87) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (84.19,247.64) – (84.19,235.92) ;
[shift=(84.19,233.92), rotate = 90] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (83.61,202.32) – (83.61,214.04) ;
[shift=(83.61,216.04), rotate = 270] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (57.35,226.25) – (26.2,226.25) ;
[shift=(59.35,226.25), rotate = 180] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (66.17,192.17) – (37,192.17) ;
[shift=(68.17,192.17), rotate = 180] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (127.33,192.67) – (103.27,192.67) ;
[shift=(101.27,192.67), rotate = 360] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ][line width=1.5]  (211.47,221.16) – (211.47,228.25) .. controls (211.47,230.21) and (221.25,231.8) .. (233.32,231.8) .. controls (245.39,231.8) and (255.18,230.21) .. (255.18,228.25) – (255.18,221.16) .. controls (255.18,219.2) and (245.39,217.61) .. (233.32,217.61) .. controls (221.25,217.61) and (211.47,219.2) .. (211.47,221.16) .. controls (211.47,223.12) and (221.25,224.7) .. (233.32,224.7) .. controls (245.39,224.7) and (255.18,223.12) .. (255.18,221.16) ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (234.25,227.86) .. controls (234.25,227.26) and (233.77,226.79) .. (233.18,226.79) .. controls (232.59,226.79) and (232.11,227.26) .. (232.11,227.86) .. controls (232.11,228.45) and (232.59,228.93) .. (233.18,228.93) .. controls (233.77,228.93) and (234.25,228.45) .. (234.25,227.86) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (230.45,227.86) .. controls (230.45,227.26) and (229.97,226.79) .. (229.38,226.79) .. controls (228.79,226.79) and (228.31,227.26) .. (228.31,227.86) .. controls (228.31,228.45) and (228.79,228.93) .. (229.38,228.93) .. controls (229.97,228.93) and (230.45,228.45) .. (230.45,227.86) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (238.04,227.86) .. controls (238.04,227.26) and (237.56,226.79) .. (236.97,226.79) .. controls (236.38,226.79) and (235.9,227.26) .. (235.9,227.86) .. controls (235.9,228.45) and (236.38,228.93) .. (236.97,228.93) .. controls (237.56,228.93) and (238.04,228.45) .. (238.04,227.86) – cycle ;

(298.02,213.03) – (296.28,202.46) – (284.28,202.46) – (282.55,213.03) – cycle ;

(296.28,202.46) – (294.93,193.62) – (285.63,193.62) – (284.28,202.46) – cycle ;

(294.93,193.62) – (294.93,185.83) – (285.63,185.83) – (285.63,193.62) – cycle ;

(294.93,185.83) – (294.93,175.7) – (285.63,175.7) – (285.63,185.83) – cycle ;

(296.28,202.46) – (282.55,213.03) ;

(298.02,213.03) – (284.28,202.46) ;

(296.28,202.46) – (285.63,193.62) ;

(284.28,202.46) – (294.93,193.62) ;

(285.63,193.62) – (294.93,185.83) ;

(294.93,193.62) – (285.63,185.83) ;

(294.93,185.83) – (285.63,175.7) ;

(285.63,185.83) – (294.93,175.7) ;

(285.63,179.5) – (272.56,185.83) – (285.63,185.83) – cycle ;

(285.63,185.83) – (281.35,181.57) ;

(276.02,185.97) – (276.02,188.1) ;

(294.93,179.5) – (308,185.83) – (294.93,185.83) – cycle ;

(299.08,181.83) – (294.93,185.83) ;

(304.42,185.97) – (304.42,188.1) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (290.53,225.33) – (290.53,216.67) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (189.2,195.03) – (189.2,260.53) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (189.2,260.53) – (211.07,260.53) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (232.34,247.3) – (232.34,235.59) ;
[shift=(232.34,233.59), rotate = 90] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (232.92,201.99) – (232.92,213.7) ;
[shift=(232.92,215.7), rotate = 270] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (251.18,194.59) – (279.83,194.59) ;
[shift=(249.18,194.59), rotate = 0] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (259,225.33) – (290.53,225.33) ;
[shift=(257,225.33), rotate = 0] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (189.2,195.03) – (213.27,195.03) ;
[shift=(215.27,195.03), rotate = 180] [fill=rgb, 255:red, 155; green, 155; blue, 155   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.4,-2.1) – (0,0) – (8.4,2.1) – cycle    ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (240.32,250.59) .. controls (240.32,247.5) and (242.82,245) .. (245.91,245) .. controls (248.99,245) and (251.5,247.5) .. (251.5,250.59) .. controls (251.5,253.68) and (248.99,256.18) .. (245.91,256.18) .. controls (242.82,256.18) and (240.32,253.68) .. (240.32,250.59) – cycle ;

(252.91,250.53) .. controls (252.91,250.52) and (252.92,250.52) .. (252.93,250.52) – (255.62,250.52) .. controls (255.63,250.52) and (255.64,250.52) .. (255.64,250.53) – (255.64,250.59) .. controls (255.64,250.6) and (255.63,250.61) .. (255.62,250.61) – (252.93,250.61) .. controls (252.92,250.61) and (252.91,250.6) .. (252.91,250.59) – cycle ;

(237.5,245.68) .. controls (237.5,245.67) and (237.51,245.67) .. (237.52,245.68) – (239.85,247.02) .. controls (239.86,247.03) and (239.86,247.04) .. (239.86,247.05) – (239.83,247.1) .. controls (239.83,247.1) and (239.82,247.11) .. (239.81,247.1) – (237.47,245.75) .. controls (237.47,245.75) and (237.46,245.74) .. (237.47,245.73) – cycle ;

(240.83,242.23) .. controls (240.84,242.23) and (240.85,242.23) .. (240.86,242.24) – (242.2,244.57) .. controls (242.21,244.58) and (242.2,244.59) .. (242.2,244.6) – (242.15,244.62) .. controls (242.14,244.63) and (242.13,244.63) .. (242.12,244.62) – (240.78,242.28) .. controls (240.77,242.28) and (240.78,242.26) .. (240.78,242.26) – cycle ;

(245.89,240.87) .. controls (245.9,240.87) and (245.91,240.88) .. (245.91,240.89) – (245.91,243.58) .. controls (245.91,243.59) and (245.9,243.6) .. (245.89,243.6) – (245.83,243.6) .. controls (245.82,243.6) and (245.82,243.59) .. (245.82,243.58) – (245.82,240.89) .. controls (245.82,240.88) and (245.82,240.87) .. (245.83,240.87) – cycle ;

(236.19,250.52) .. controls (236.19,250.51) and (236.2,250.5) .. (236.21,250.5) – (238.9,250.5) .. controls (238.91,250.5) and (238.92,250.51) .. (238.92,250.52) – (238.92,250.57) .. controls (238.92,250.58) and (238.91,250.59) .. (238.9,250.59) – (236.21,250.59) .. controls (236.2,250.59) and (236.19,250.58) .. (236.19,250.57) – cycle ;

(249.44,256.5) .. controls (249.45,256.49) and (249.46,256.5) .. (249.47,256.51) – (250.82,258.84) .. controls (250.82,258.85) and (250.82,258.86) .. (250.81,258.86) – (250.76,258.89) .. controls (250.75,258.9) and (250.74,258.89) .. (250.74,258.88) – (249.39,256.55) .. controls (249.39,256.54) and (249.39,256.53) .. (249.4,256.53) – cycle ;

(245.98,257.57) .. controls (245.99,257.57) and (246,257.58) .. (246,257.59) – (246,260.29) .. controls (246,260.3) and (245.99,260.3) .. (245.98,260.3) – (245.92,260.3) .. controls (245.91,260.3) and (245.91,260.3) .. (245.91,260.29) – (245.91,257.59) .. controls (245.91,257.58) and (245.91,257.57) .. (245.92,257.57) – cycle ;

(252.03,253.89) .. controls (252.04,253.88) and (252.05,253.88) .. (252.06,253.89) – (254.39,255.23) .. controls (254.4,255.24) and (254.4,255.25) .. (254.4,255.26) – (254.37,255.31) .. controls (254.36,255.31) and (254.35,255.32) .. (254.34,255.31) – (252.01,253.96) .. controls (252,253.96) and (252,253.95) .. (252,253.94) – cycle ;

(250.81,242.22) .. controls (250.82,242.23) and (250.82,242.24) .. (250.82,242.25) – (249.47,244.58) .. controls (249.46,244.59) and (249.45,244.59) .. (249.44,244.59) – (249.4,244.56) .. controls (249.39,244.56) and (249.39,244.54) .. (249.39,244.54) – (250.74,242.2) .. controls (250.74,242.19) and (250.75,242.19) .. (250.76,242.2) – cycle ;

(254.4,245.61) .. controls (254.4,245.62) and (254.4,245.63) .. (254.39,245.63) – (252.06,246.98) .. controls (252.05,246.98) and (252.04,246.98) .. (252.03,246.97) – (252,246.93) .. controls (252,246.92) and (252,246.91) .. (252.01,246.9) – (254.34,245.55) .. controls (254.35,245.55) and (254.36,245.55) .. (254.37,245.56) – cycle ;

(239.86,253.82) .. controls (239.86,253.83) and (239.86,253.84) .. (239.85,253.84) – (237.52,255.19) .. controls (237.51,255.19) and (237.5,255.19) .. (237.5,255.18) – (237.47,255.14) .. controls (237.46,255.13) and (237.47,255.12) .. (237.47,255.11) – (239.81,253.76) .. controls (239.82,253.76) and (239.83,253.76) .. (239.83,253.77) – cycle ;

(242.06,256.49) .. controls (242.07,256.49) and (242.07,256.51) .. (242.07,256.51) – (240.72,258.85) .. controls (240.72,258.86) and (240.71,258.86) .. (240.7,258.85) – (240.65,258.83) .. controls (240.64,258.82) and (240.64,258.81) .. (240.64,258.8) – (241.99,256.47) .. controls (241.99,256.46) and (242.01,256.46) .. (242.01,256.46) – cycle ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (218.73,267.55) – (222.13,250.48) – (245.21,250.48) – (248.61,267.55) – cycle ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (219.98,262.04) – (247.58,261.99) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (220.94,256.09) – (246.02,256.09) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (237.21,250.97) – (239.45,267.81) ;

[color=rgb, 255:red, 255; green, 255; blue, 255   ,draw opacity=1 ][fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ]   (230.13,250.81) – (228.13,267.93) ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (219.11,186.04) – (245.25,186.04) – (245.25,198.8) – (219.11,198.8) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (226.57,187.45) – (223.92,187.45) – (223.92,189.32) – (222.06,189.32) – (222.06,191.96) – (223.92,191.96) – (223.92,193.83) – (226.57,193.83) – (226.57,191.96) – (228.44,191.96) – (228.44,189.32) – (226.57,189.32) – cycle ;

[fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (235.67,189.18) – (242.1,189.18) – (242.1,192.05) – (235.67,192.05) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (223.77,182.74) – (227.03,182.74) – (227.03,183.73) – (223.77,183.73) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (237.63,182.74) – (240.9,182.74) – (240.9,183.73) – (237.63,183.73) – cycle ;

(130.57,138.67) – (182.43,138.67) – (182.43,164.67) – (130.57,164.67) – cycle ;

[draw opacity=0] (149.13,146.36) .. controls (150.73,143.89) and (153.52,142.25) .. (156.68,142.25) .. controls (161.64,142.25) and (165.66,146.27) .. (165.66,151.22) .. controls (165.66,152.13) and (165.52,153) .. (165.27,153.83) – (156.68,151.22) – cycle ; (149.13,146.36) .. controls (150.73,143.89) and (153.52,142.25) .. (156.68,142.25) .. controls (161.64,142.25) and (165.66,146.27) .. (165.66,151.22) ; [shift=(165.27,153.83), rotate = 274.15] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (5.36,-2.57) – (0,0) – (5.36,2.57) – (3.56,0) – cycle    ;

[draw opacity=0] (164.23,156.09) .. controls (162.63,158.56) and (159.85,160.2) .. (156.68,160.2) .. controls (151.72,160.2) and (147.7,156.18) .. (147.7,151.22) .. controls (147.7,150.32) and (147.84,149.44) .. (148.09,148.62) – (156.68,151.22) – cycle ; (164.23,156.09) .. controls (162.63,158.56) and (159.85,160.2) .. (156.68,160.2) .. controls (151.72,160.2) and (147.7,156.18) .. (147.7,151.22) ; [shift=(148.09,148.62), rotate = 94.15] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (5.36,-2.57) – (0,0) – (5.36,2.57) – (3.56,0) – cycle    ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (156.68,151.22) – (158.27,151.25) – (154.49,157.8) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (156.68,151.22) – (155.1,151.2) – (158.88,144.65) – cycle ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (149.67,131.71) – (149.67,136.53) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (86.07,158.53) – (125.67,158.53) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (86.07,158.53) – (86.07,180.33) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (186.07,158.53) – (230.83,158.53) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (230.83,158.53) – (230.83,180) ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ][dash pattern=on 0.84pt off 2.51pt] (3.67,170.67) – (133.67,170.67) – (133.67,273.33) – (3.67,273.33) – cycle ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ][dash pattern=on 0.84pt off 2.51pt] (182,170.02) – (312.67,170.02) – (312.67,274.33) – (182,274.33) – cycle ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ][dash pattern=on 0.84pt off 2.51pt] (90.33,3) – (247,3) – (247,134.2) – (90.33,134.2) – cycle ;

[color=rgb, 255:red, 155; green, 155; blue, 155   ,draw opacity=1 ]   (26.2,226.25) – (26.2,215.73) ;

(142,167) node [anchor=north west][inner sep=0.75pt]   [align=left] BMS;

(102, 34.23) node [anchor=north west][inner sep=0.75pt]   [align=left] Renewable source;

(132,75) node [anchor=north west][inner sep=0.75pt]   [align=left] server;

(132,118) node [anchor=north west][inner sep=0.75pt]   [align=left] Battery;

(214.3, 62) node [anchor=north west][inner sep=0.75pt]   [align=left] Grid;

The figure shows the system model, where the arrows represent the directions of energy flow.

§.§ System Model

Fig. <ref> shows $S$ sites (illustrated by dashed rectangles) forming an edge computing network. Let $\mathcal{S} = \{1,2,...,S\}$. Each site consists of an edge computing server, a battery, a local renewable energy source, and the local power grid. The servers have the same specification and computing power. The batteries are connected to each other via a battery management system (BMS), hence the energy in a battery can be shared with the servers on the other sites[The BMS has been studies widely, see for example [12] and [13].]. In this paper, we use the index of the site to refer to its components, e.g., server $s$, battery $s$, etc. More specifics of the system model are as follows;

* A server can be powered by its local grid, its renewable energy source, and all the batteries.

* A local battery can be charged by the local grid and the local renewable energy source. Additionally, the battery can provide energy to any other server. However, this comes with an energy transfer loss.

§.§ Time Horizon

We consider a scheduling horizon of $T$ time slots, denoted by $\mathcal{T} = \{1,2,...,T\}$. The set of tasks over the entire time horizon is represented by $\mathcal{N} = \{1, 2, ..., N\}$. In this paper, the tasks are assumed to be of the same type, i.e., the amount of energy to complete them is uniform, denoted by $E$. Without loss of generality, we use $E$ as our energy unit, and the relevant parameters (e.g., parameters $R$, $I$, $\alpha$, $\beta$, $L$, and $H$ to be introduced next) are all normalized by $E$, i.e., they are specified in multiples of $E$.

Task $n$ is represented by a tuple $(o_n, d_n, s_n, \mathcal{S}_n)$, where $o_n, d_n \in \mathcal{T}, s_n \in \mathcal{S}, \mathcal{S}_n \subseteq \mathcal{S}$, such that

* $o_n$ is the time slot when the task is generated;

* $d_n$ is the deadline of completing the task;

* $s_n$ is the server that the task is initially associated with;

* $\mathcal{S}_n$ represents the set of candidate servers[Some tasks might not be suitable for some servers because of, for example, latency due to the distance.] that can perform task $n$.

A task is to be completed in some time slot in the interval $[o_n, d_n]$.

Denote by $\pi_{nst}$ a binary variable that is one if and only if task $n$ is completed by server $s$ in time slot $t$. For any task, it needs to be completed once, thus we have

\begin{equation}\label{Constraint_1}
\sum_{s \in \mathcal{S}} \sum^{d_n}_{t = o_n} \pi_{nst} = 1, \forall n \in \mathcal{N}.
\end{equation}

Due to normalization, a task requires one unit of energy. Thus in time slot $t$, the amount of energy consumed for task completion by server $s$ is $\sum_{n \in \mathcal{N}} \pi_{nst}$. Of the energy consumed, we use variables $x_{st}$, $y_{ss^\prime t}$, and $z_{st}$ to represent the amount of energy (again normalized by $E$) by server $s$ from the local grid, battery $s^\prime$, and the local renewable source, respectively, in time slot $t$. Then we have

\begin{equation}\label{Constraint_2}
x_{st} + \sum_{s^\prime \in S}  y _{ss^\prime t} + z_{st} = \sum_{n \in \mathcal{N}} \pi_{nst}, \forall s \in \mathcal{S}, t \in \mathcal{T}.
\end{equation}

In addition, the maximum number of tasks that a server can perform in a time slot is constrained by the computing capacity, denoted by $H$. As a task amounts to one energy unit, we have the following constraint:

\begin{equation}\label{Constraint_3}
x_{st}+\sum_{s^\prime \in\mathcal{S}} y_{ss^\prime t} +z_{st} \leq H, \forall s \in \mathcal{S}, t \in \mathcal{T}.
\end{equation}

We use variables $u_{st}$ and $v_{st}$ to represent the amount of energy from the local grid and the renewable source for charging, respectively. In addition, denote by variable $w_{st}$ the amount of remaining energy of battery $s$ at the end of time slot $t$. We use $L$ to denote the battery capacity. In time slot $t$, we have the following battery capacity constraint:

\begin{equation}\label{Constraint_4}
u_{st} + v_{st} + w_{s(t-1)} \leq L, \forall s \in \mathcal{S}, t \in \mathcal{T} \setminus \{1\}.
\end{equation}

By the end of time slot $t$, the remaining energy $w_{st}$ is given by

\begin{equation}\label{Constraint_5}
w_{st} = u_{st} + v_{st} + w_{s(t-1)} -\sum_{s^\prime \in \mathcal{S}} y_{ss^\prime t}, \forall s \in \mathcal{S}, t \in \mathcal{T} \setminus \{1\}.
\end{equation}

We use $R_{st}$ to denote the amount of renewable energy[Renewable energy can be predicted via for examples methods in [14].] available from source $s$ in time slot $t$. The renewable energy is used for charging the local battery and supplying the local server, thus we have

\begin{equation}\label{Constraint_6}
z_{st} + u_{st} \leq R_{st}, \forall s \in \mathcal{S}, t \in \mathcal{T}.
\end{equation}

§.§ Carbon Footprint and Mathematical Formulation

In the system model, CF occurs in three processes related to the grids. Denote by $I_{st}$ the CI of local grid $s$ in time slot $t$. The three types of CF can be calculated as follows.

* Task completion: CF will occur when a server consumes the energy from the local grid to complete some task. The total amount of CF of this can be expressed as

\begin{equation}\label{CF_task_completion}
\text{CF}^{\text{G}}(\boldsymbol{x}) = \sum_{t \in \mathcal{T}} \sum_{s\in \mathcal{S}} I_{st}x_{st}.
\end{equation}

* Battery charging: The total amount of CF due to battery charging via the local grid can be calculated by

\begin{equation}\label{CF_battery_charging}
\text{CF}^{\text{B}}(\boldsymbol{u}) = \sum_{t \in \mathcal{T}} \sum_{s\in \mathcal{S}} I_{st}u_{st}.
\end{equation}

* Task offloading: In this paper, we consider the worst-case CF in task offloading, i.e., we assume that the energy used for task offloading is entirely from the grid. We use $\alpha_{s_n s}$ to represent the required amount of the energy for transferring task $n$ from its initial server $s_n$ to $s$ ($\alpha_{s_n s} = 0$ if $s_n = s$). The total CF of task offloading in the network is given by

\begin{align}\label{CF_task_offloading}
\text{CF}^{\text{O}}(\boldsymbol{\pi}) =  \sum_{n \in \mathcal{N}} \sum_{s \in \mathcal{S}_n}  \sum^{d_n}_{t = o_n} \alpha_{s_n s} I_{st}  \pi_{nst}.
\end{align}

In addition, there will be some loss in energy transfer between a battery and the servers of other sites. We convert this loss into an equivalent amount of CF. Denote the loss per unit of energy from battery $s^\prime$ to server $s$ by $\beta_{s^\prime s}$ ($\beta_{s^\prime s} = 0$ if $s^\prime = s$). We assume that local grid $s$ provides energy to make up for the loss, and the total amount of the equivalent CF is thus

\begin{equation}\label{CF_energy_loss}
\text{CF}^{\text{L}}(\boldsymbol{y}) = \sum_{s \in \mathcal{S}}  \sum_{t \in \mathcal{T}}\sum_{s^\prime \in S_n}  \beta_{s^\prime s} I_{st} y _{ss^\prime t}.
\end{equation}

We consider minimizing the total CF in the edge computing network. The CF minimization problem can be formulated by integer linear programming (ILP) as follows,

\begin{align}
\mathop{\min}_{\boldsymbol{\pi} \in \{0,1\}, \atop \boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}, \boldsymbol{u}, \boldsymbol{v}, \boldsymbol{w} \geq 0} \ & \text{CF}^{\text{G}}(\boldsymbol{x}) +  \text{CF}^{\text{B}}(\boldsymbol{u}) + \text{CF}^{\text{O}}(\boldsymbol{\pi}) + \text{CF}^{\text{L}}(\boldsymbol{y}) \label{obj}\\
\text{s.t.} & \quad \eqref{Constraint_1} \text{-} \eqref{Constraint_6},\notag
\end{align}

where the objective function (<ref>) is the overall system CF.

§ PROBLEM SOLVING

every picture/.style=line width=0.75pt

(0,30) rectangle (590, 430);

[color=rgb, 255:red, 0; green, 0; blue, 0   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=0.8 ][dash pattern=on 0.84pt off 2.51pt] (495.67,30.5) – (542,30.5) – (542,342.5) – (495.67,342.5) – cycle ;

[color=rgb, 255:red, 0; green, 0; blue, 0   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=0.8 ][dash pattern=on 0.84pt off 2.51pt] (254.33,30) – (484.67,30) – (484.67,342.5) – (254.33,342.5) – cycle ;

(300,404.43) .. controls (369.9,384.35) and (349.57,363.21) .. (417.87,276.92) ;
[shift=(418.9,275.62), rotate = 128.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(301.29,407) .. controls (374.13,385.11) and (359.65,359.92) .. (418.3,299.34) ;
[shift=(419.19,298.43), rotate = 133.69] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(301.6,409.6) .. controls (370.64,391.76) and (375.44,350.65) .. (416.83,332.45) ;
[shift=(418.09,331.91), rotate = 155.81] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(299.57,415.14) .. controls (512.33,403.83) and (566,460.4) .. (571.97,219.33) ;
[shift=(571.97,219.33), rotate = 91.42] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 0; green, 0; blue, 0   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=0.8 ][dash pattern=on 0.84pt off 2.51pt] (312.5,355.08) – (587.56,355.08) – (587.56,388.33) – (312.5,388.33) – cycle ;

[color=rgb, 255:red, 0; green, 0; blue, 0   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=0.8 ][dash pattern=on 0.84pt off 2.51pt] (13.13,31) – (242.4,31) – (242.4,342.9) – (13.13,342.9) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (55.83,182.33) .. controls (55.83,177.09) and (60.09,172.83) .. (65.33,172.83) .. controls (70.58,172.83) and (74.83,177.09) .. (74.83,182.33) .. controls (74.83,187.58) and (70.58,191.83) .. (65.33,191.83) .. controls (60.09,191.83) and (55.83,187.58) .. (55.83,182.33) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (101.17,182.33) .. controls (101.17,177.09) and (105.42,172.83) .. (110.67,172.83) .. controls (115.91,172.83) and (120.17,177.09) .. (120.17,182.33) .. controls (120.17,187.58) and (115.91,191.83) .. (110.67,191.83) .. controls (105.42,191.83) and (101.17,187.58) .. (101.17,182.33) – cycle ;

(74.83,182.33) – (99.17,182.33) ;
[shift=(101.17,182.33), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (55.8,205.83) .. controls (55.8,200.59) and (60.05,196.33) .. (65.3,196.33) .. controls (70.55,196.33) and (74.8,200.59) .. (74.8,205.83) .. controls (74.8,211.08) and (70.55,215.33) .. (65.3,215.33) .. controls (60.05,215.33) and (55.8,211.08) .. (55.8,205.83) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (101.13,205.83) .. controls (101.13,200.59) and (105.39,196.33) .. (110.63,196.33) .. controls (115.88,196.33) and (120.13,200.59) .. (120.13,205.83) .. controls (120.13,211.08) and (115.88,215.33) .. (110.63,215.33) .. controls (105.39,215.33) and (101.13,211.08) .. (101.13,205.83) – cycle ;

(74.8,205.83) – (99.13,205.83) ;
[shift=(101.13,205.83), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (55.8,242.67) .. controls (55.8,237.42) and (60.05,233.17) .. (65.3,233.17) .. controls (70.55,233.17) and (74.8,237.42) .. (74.8,242.67) .. controls (74.8,247.91) and (70.55,252.17) .. (65.3,252.17) .. controls (60.05,252.17) and (55.8,247.91) .. (55.8,242.67) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (101.13,242.67) .. controls (101.13,237.42) and (105.39,233.17) .. (110.63,233.17) .. controls (115.88,233.17) and (120.13,237.42) .. (120.13,242.67) .. controls (120.13,247.91) and (115.88,252.17) .. (110.63,252.17) .. controls (105.39,252.17) and (101.13,247.91) .. (101.13,242.67) – cycle ;

(74.8,242.67) – (99.13,242.67) ;
[shift=(101.13,242.67), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 126; green, 211; blue, 33   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (15,95.5) .. controls (15,90.25) and (19.25,86) .. (24.5,86) .. controls (29.75,86) and (34,90.25) .. (34,95.5) .. controls (34,100.75) and (29.75,105) .. (24.5,105) .. controls (19.25,105) and (15,100.75) .. (15,95.5) – cycle ;

[color=rgb, 255:red, 126; green, 211; blue, 33   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (15,118.8) .. controls (15,113.55) and (19.25,109.3) .. (24.5,109.3) .. controls (29.75,109.3) and (34,113.55) .. (34,118.8) .. controls (34,124.05) and (29.75,128.3) .. (24.5,128.3) .. controls (19.25,128.3) and (15,124.05) .. (15,118.8) – cycle ;

[color=rgb, 255:red, 126; green, 211; blue, 33   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (15,155.8) .. controls (15,150.55) and (19.25,146.3) .. (24.5,146.3) .. controls (29.75,146.3) and (34,150.55) .. (34,155.8) .. controls (34,161.05) and (29.75,165.3) .. (24.5,165.3) .. controls (19.25,165.3) and (15,161.05) .. (15,155.8) – cycle ;

(31.25,102.75) – (60.96,171.41) ;
[shift=(61.75,173.25), rotate = 246.61] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(29.5,127.3) – (57.5,196.89) ;
[shift=(58.25,198.75), rotate = 248.08] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(30.75,163.25) – (58.51,232.89) ;
[shift=(59.25,234.75), rotate = 248.27] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(284.3,415.2) .. controls (-13.67,427.61) and (4.87,335.7) .. (56.75,187.25) ;
[shift=(56.75,187.25), rotate = 109.22] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (177,269.5) .. controls (177,264.25) and (181.25,260) .. (186.5,260) .. controls (191.75,260) and (196,264.25) .. (196,269.5) .. controls (196,274.75) and (191.75,279) .. (186.5,279) .. controls (181.25,279) and (177,274.75) .. (177,269.5) – cycle ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (177,292.8) .. controls (177,287.55) and (181.25,283.3) .. (186.5,283.3) .. controls (191.75,283.3) and (196,287.55) .. (196,292.8) .. controls (196,298.05) and (191.75,302.3) .. (186.5,302.3) .. controls (181.25,302.3) and (177,298.05) .. (177,292.8) – cycle ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (177,329.8) .. controls (177,324.55) and (181.25,320.3) .. (186.5,320.3) .. controls (191.75,320.3) and (196,324.55) .. (196,329.8) .. controls (196,335.05) and (191.75,339.3) .. (186.5,339.3) .. controls (181.25,339.3) and (177,335.05) .. (177,329.8) – cycle ;

(119.6,185.6) – (178.42,261.35) ;
[shift=(179.64,262.93), rotate = 232.17] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(117.8,188.6) – (178.29,284.1) ;
[shift=(179.36,285.79), rotate = 237.65] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(115.6,190.8) – (181.86,318.58) ;
[shift=(182.79,320.36), rotate = 242.59] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(119.2,209.8) – (175.92,264.68) ;
[shift=(177.36,266.07), rotate = 224.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(117.2,212.6) – (175.93,287.92) ;
[shift=(177.16,289.5), rotate = 232.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(114.6,214.6) – (178.33,321.5) ;
[shift=(179.36,323.21), rotate = 239.2] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(119.6,246.4) – (175.14,268.75) ;
[shift=(177,269.5), rotate = 201.92] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(117.6,249) – (175.39,291.61) ;
[shift=(177,292.8), rotate = 216.4] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(115,251.6) – (176.07,324.54) ;
[shift=(177.36,326.07), rotate = 230.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 126; green, 211; blue, 33   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (282.6,409.6) .. controls (282.6,404.35) and (286.85,400.1) .. (292.1,400.1) .. controls (297.35,400.1) and (301.6,404.35) .. (301.6,409.6) .. controls (301.6,414.85) and (297.35,419.1) .. (292.1,419.1) .. controls (286.85,419.1) and (282.6,414.85) .. (282.6,409.6) – cycle ;

(120.17,182.5) – (295.17,182.5) ;
[shift=(297.17,182.5), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(120.13,205.83) – (295.13,205.83) ;
[shift=(297.13,205.83), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(120.13,242.83) – (295.13,242.83) ;
[shift=(297.13,242.83), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(16,99.67) .. controls (-7.33,195.75) and (-2.33,317.75) .. (176.4,272.47) ;
[shift=(176.4,272.47), rotate = 166.92] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(17.38,125.63) .. controls (10.67,161.75) and (-16.44,301.17) .. (176.88,294.13) ;
[shift=(176.88,294.13), rotate = 180.48] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(18.83,164) .. controls (12.7,232.41) and (61.38,293.02) .. (174.86,327.9) ;
[shift=(176.57,328.43), rotate = 197.52] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (297.33,183.5) .. controls (297.33,178.25) and (301.59,174) .. (306.83,174) .. controls (312.08,174) and (316.33,178.25) .. (316.33,183.5) .. controls (316.33,188.75) and (312.08,193) .. (306.83,193) .. controls (301.59,193) and (297.33,188.75) .. (297.33,183.5) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (342.67,183.5) .. controls (342.67,178.25) and (346.92,174) .. (352.17,174) .. controls (357.41,174) and (361.67,178.25) .. (361.67,183.5) .. controls (361.67,188.75) and (357.41,193) .. (352.17,193) .. controls (346.92,193) and (342.67,188.75) .. (342.67,183.5) – cycle ;

(316.33,183.5) – (340.67,183.5) ;
[shift=(342.67,183.5), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (297.3,206.83) .. controls (297.3,201.59) and (301.55,197.33) .. (306.8,197.33) .. controls (312.05,197.33) and (316.3,201.59) .. (316.3,206.83) .. controls (316.3,212.08) and (312.05,216.33) .. (306.8,216.33) .. controls (301.55,216.33) and (297.3,212.08) .. (297.3,206.83) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (342.63,206.83) .. controls (342.63,201.59) and (346.89,197.33) .. (352.13,197.33) .. controls (357.38,197.33) and (361.63,201.59) .. (361.63,206.83) .. controls (361.63,212.08) and (357.38,216.33) .. (352.13,216.33) .. controls (346.89,216.33) and (342.63,212.08) .. (342.63,206.83) – cycle ;

(316.3,206.83) – (340.63,206.83) ;
[shift=(342.63,206.83), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (297.3,243.83) .. controls (297.3,238.59) and (301.55,234.33) .. (306.8,234.33) .. controls (312.05,234.33) and (316.3,238.59) .. (316.3,243.83) .. controls (316.3,249.08) and (312.05,253.33) .. (306.8,253.33) .. controls (301.55,253.33) and (297.3,249.08) .. (297.3,243.83) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 27   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (342.63,243.83) .. controls (342.63,238.59) and (346.89,234.33) .. (352.13,234.33) .. controls (357.38,234.33) and (361.63,238.59) .. (361.63,243.83) .. controls (361.63,249.08) and (357.38,253.33) .. (352.13,253.33) .. controls (346.89,253.33) and (342.63,249.08) .. (342.63,243.83) – cycle ;

(316.3,243.83) – (340.63,243.83) ;
[shift=(342.63,243.83), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 126; green, 211; blue, 33   ,draw opacity=1 ] (256.5,96.5) .. controls (256.5,91.25) and (260.75,87) .. (266,87) .. controls (271.25,87) and (275.5,91.25) .. (275.5,96.5) .. controls (275.5,101.75) and (271.25,106) .. (266,106) .. controls (260.75,106) and (256.5,101.75) .. (256.5,96.5) – cycle ;

[color=rgb, 255:red, 126; green, 211; blue, 33   ,draw opacity=1 ] (256.5,119.8) .. controls (256.5,114.55) and (260.75,110.3) .. (266,110.3) .. controls (271.25,110.3) and (275.5,114.55) .. (275.5,119.8) .. controls (275.5,125.05) and (271.25,129.3) .. (266,129.3) .. controls (260.75,129.3) and (256.5,125.05) .. (256.5,119.8) – cycle ;

[color=rgb, 255:red, 126; green, 211; blue, 33   ,draw opacity=1 ] (256.5,156.8) .. controls (256.5,151.55) and (260.75,147.3) .. (266,147.3) .. controls (271.25,147.3) and (275.5,151.55) .. (275.5,156.8) .. controls (275.5,162.05) and (271.25,166.3) .. (266,166.3) .. controls (260.75,166.3) and (256.5,162.05) .. (256.5,156.8) – cycle ;

(272.75,103.75) – (302.46,172.41) ;
[shift=(303.25,174.25), rotate = 246.61] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(271,128.3) – (299,197.89) ;
[shift=(299.75,199.75), rotate = 248.08] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(272.25,164.25) – (300.01,233.89) ;
[shift=(300.75,235.75), rotate = 248.27] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (418.5,270.5) .. controls (418.5,265.25) and (422.75,261) .. (428,261) .. controls (433.25,261) and (437.5,265.25) .. (437.5,270.5) .. controls (437.5,275.75) and (433.25,280) .. (428,280) .. controls (422.75,280) and (418.5,275.75) .. (418.5,270.5) – cycle ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (418.5,293.8) .. controls (418.5,288.55) and (422.75,284.3) .. (428,284.3) .. controls (433.25,284.3) and (437.5,288.55) .. (437.5,293.8) .. controls (437.5,299.05) and (433.25,303.3) .. (428,303.3) .. controls (422.75,303.3) and (418.5,299.05) .. (418.5,293.8) – cycle ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (418.5,330.8) .. controls (418.5,325.55) and (422.75,321.3) .. (428,321.3) .. controls (433.25,321.3) and (437.5,325.55) .. (437.5,330.8) .. controls (437.5,336.05) and (433.25,340.3) .. (428,340.3) .. controls (422.75,340.3) and (418.5,336.05) .. (418.5,330.8) – cycle ;

(361.1,186.6) – (419.92,262.35) ;
[shift=(421.14,263.93), rotate = 232.17] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(359.3,189.6) – (419.79,285.1) ;
[shift=(420.86,286.79), rotate = 237.65] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(357.1,191.8) – (423.36,319.58) ;
[shift=(424.29,321.36), rotate = 242.59] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(360.7,210.8) – (417.42,265.68) ;
[shift=(418.86,267.07), rotate = 224.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(358.7,213.6) – (417.43,288.92) ;
[shift=(418.66,290.5), rotate = 232.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(356.1,215.6) – (419.83,322.5) ;
[shift=(420.86,324.21), rotate = 239.2] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(361.1,247.4) – (416.64,269.75) ;
[shift=(418.5,270.5), rotate = 201.92] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(359.1,250) – (416.89,292.61) ;
[shift=(418.5,293.8), rotate = 216.4] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(356.5,252.6) – (417.57,325.54) ;
[shift=(418.86,327.07), rotate = 230.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(257.5,101) .. controls (236.67,179.75) and (243.67,295.75) .. (417.9,273.8) ;
[shift=(417.9,273.8), rotate = 173.98] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(258.88,126.63) .. controls (253.17,154.75) and (228.67,291.25) .. (418.38,295.13) ;
[shift=(418.38,295.13), rotate = 184.2] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(261.17,165.5) .. controls (264.67,241.75) and (283.38,281.25) .. (418.07,329.43) ;
[shift=(418.07,329.43), rotate = 200.06] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(196,269.5) – (220.33,269.5) ;
[shift=(222.33,269.5), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (222.33,269.5) .. controls (222.33,264.25) and (226.59,260) .. (231.83,260) .. controls (237.08,260) and (241.33,264.25) .. (241.33,269.5) .. controls (241.33,274.75) and (237.08,279) .. (231.83,279) .. controls (226.59,279) and (222.33,274.75) .. (222.33,269.5) – cycle ;

(196,292.8) – (220.33,292.8) ;
[shift=(222.33,292.8), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (222.33,292.8) .. controls (222.33,287.55) and (226.59,283.3) .. (231.83,283.3) .. controls (237.08,283.3) and (241.33,287.55) .. (241.33,292.8) .. controls (241.33,298.05) and (237.08,302.3) .. (231.83,302.3) .. controls (226.59,302.3) and (222.33,298.05) .. (222.33,292.8) – cycle ;

(196,329.8) – (220.33,329.8) ;
[shift=(222.33,329.8), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (222.33,329.8) .. controls (222.33,324.55) and (226.59,320.3) .. (231.83,320.3) .. controls (237.08,320.3) and (241.33,324.55) .. (241.33,329.8) .. controls (241.33,335.05) and (237.08,339.3) .. (231.83,339.3) .. controls (226.59,339.3) and (222.33,335.05) .. (222.33,329.8) – cycle ;

(437.5,270.5) – (461.83,270.5) ;
[shift=(463.83,270.5), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(437.5,293.8) – (461.83,293.8) ;
[shift=(463.83,293.8), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(437.5,330.8) – (461.83,330.8) ;
[shift=(463.83,330.8), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (463.83,270.5) .. controls (463.83,265.25) and (468.09,261) .. (473.33,261) .. controls (478.58,261) and (482.83,265.25) .. (482.83,270.5) .. controls (482.83,275.75) and (478.58,280) .. (473.33,280) .. controls (468.09,280) and (463.83,275.75) .. (463.83,270.5) – cycle ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (463.83,293.8) .. controls (463.83,288.55) and (468.09,284.3) .. (473.33,284.3) .. controls (478.58,284.3) and (482.83,288.55) .. (482.83,293.8) .. controls (482.83,299.05) and (478.58,303.3) .. (473.33,303.3) .. controls (468.09,303.3) and (463.83,299.05) .. (463.83,293.8) – cycle ;

[color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (463.83,330.8) .. controls (463.83,325.55) and (468.09,321.3) .. (473.33,321.3) .. controls (478.58,321.3) and (482.83,325.55) .. (482.83,330.8) .. controls (482.83,336.05) and (478.58,340.3) .. (473.33,340.3) .. controls (468.09,340.3) and (463.83,336.05) .. (463.83,330.8) – cycle ;

[color=rgb, 255:red, 245; green, 166; blue, 35   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (326.47,373.5) .. controls (326.47,368.25) and (330.72,364) .. (335.97,364) .. controls (341.21,364) and (345.47,368.25) .. (345.47,373.5) .. controls (345.47,378.75) and (341.21,383) .. (335.97,383) .. controls (330.72,383) and (326.47,378.75) .. (326.47,373.5) – cycle ;

(361.67,183.25) – (499.8,183.25) ;
[shift=(501.8,183.25), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 245; green, 166; blue, 35   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (562.47,209.83) .. controls (562.47,204.59) and (566.72,200.33) .. (571.97,200.33) .. controls (577.21,200.33) and (581.47,204.59) .. (581.47,209.83) .. controls (581.47,215.08) and (577.21,219.33) .. (571.97,219.33) .. controls (566.72,219.33) and (562.47,215.08) .. (562.47,209.83) – cycle ;

[color=rgb, 255:red, 245; green, 166; blue, 35   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (465.2,373.5) .. controls (465.2,368.25) and (469.45,364) .. (474.7,364) .. controls (479.95,364) and (484.2,368.25) .. (484.2,373.5) .. controls (484.2,378.75) and (479.95,383) .. (474.7,383) .. controls (469.45,383) and (465.2,378.75) .. (465.2,373.5) – cycle ;

[color=rgb, 255:red, 245; green, 166; blue, 35   ,draw opacity=1 ][fill=rgb, 255:red, 255; green, 255; blue, 255   ,fill opacity=1 ] (515.73,373.5) .. controls (515.73,368.25) and (519.99,364) .. (525.23,364) .. controls (530.48,364) and (534.73,368.25) .. (534.73,373.5) .. controls (534.73,378.75) and (530.48,383) .. (525.23,383) .. controls (519.99,383) and (515.73,378.75) .. (515.73,373.5) – cycle ;

(240,274.4) .. controls (258.86,357.64) and (240.08,385.38) .. (325.3,375.22) ;
[shift=(326.59,375.06), rotate = 173.55] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(234.58,302.06) .. controls (256.47,328.37) and (218.58,397.93) .. (324.98,377.61) ;
[shift=(326.6,377.3), rotate = 170.91] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(235.67,338.94) .. controls (232.13,359.95) and (257.59,402.51) .. (326.93,379.42) ;
[shift=(327.97,379.06), rotate = 165.15] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(481.8,275.8) .. controls (506.4,344.4) and (491.4,379.4) .. (345.4,376.8) ;
[shift=(345.4,376.8), rotate = 0.59] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(480.2,301) .. controls (505.41,352.04) and (450.73,371.31) .. (347.03,373.47) ;
[shift=(345.47,373.5), rotate = 358.5] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(482.83,270.5) .. controls (508.8,312.17) and (501.78,335.14) .. (483.08,364.81) ;
[shift=(482.22,366.17), rotate = 302] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(482.83,293.8) .. controls (501.32,310.94) and (497.02,334.45) .. (478.73,362.55) ;
[shift=(477.89,363.83), rotate = 302.24] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(361.63,206.83) – (499.4,206.83) ;
[shift=(501.4,206.83), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(361.63,243.83) – (499,243.83) ;
[shift=(501,243.83), rotate = 180] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(283.3,413.2) .. controls (-23.46,421.57) and (23.85,316.01) .. (56.29,213.38) ;
[shift=(56.78,211.83), rotate = 107.54] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(282.75,411.04) .. controls (-29.45,414.6) and (41.79,293.36) .. (56.44,248.24) ;
[shift=(56.87,246.9), rotate = 107.6] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(282.57,407.14) .. controls (71.4,376.63) and (43.8,317.83) .. (178.6,275.6) ;
[shift=(178.6,275.6), rotate = 162.34] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(283.71,404.57) .. controls (26.29,358.86) and (96.68,307.15) .. (176.2,297.34) ;
[shift=(177.4,297.2), rotate = 172.97] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(285.43,402.86) .. controls (45.01,352.88) and (102.42,311.45) .. (175.5,331.53) ;
[shift=(176.6,331.83), rotate = 195.36] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(289.71,400.86) .. controls (272.8,342.65) and (254.58,269.34) .. (297.19,188.47) ;
[shift=(297.83,187.25), rotate = 116.83] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(292.1,400.1) .. controls (283.18,342.74) and (265.48,295.77) .. (297.84,212.02) ;
[shift=(298.33,210.75), rotate = 110.48] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(294.5,400.08) .. controls (285.26,314.94) and (284.44,301.83) .. (298.57,251.67) ;
[shift=(299,250.14), rotate = 105.68] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 0; green, 0; blue, 0   ,draw opacity=1 ]   (535.2,335.6) .. controls (535.2,346.74) and (534.09,350.25) .. (530.49,364.35) ;
[shift=(530.02,366.17), rotate = 284.41] [fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 0; green, 0; blue, 0   ,draw opacity=1 ]   (529.21,335.17) .. controls (529.95,342.68) and (527.21,352.93) .. (525.56,362.1) ;
[shift=(525.23,364), rotate = 280.74] [fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

[color=rgb, 255:red, 0; green, 0; blue, 0   ,draw opacity=1 ]   (521.6,334.93) .. controls (523.14,347.16) and (522.8,346.93) .. (521,363.11) ;
[shift=(520.8,364.93), rotate = 276.48] [fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(536,183.73) .. controls (547.09,182.61) and (552.46,205.04) .. (560.75,211.27) ;
[shift=(562.38,212.25), rotate = 225.65] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(536.55,206.36) .. controls (547.81,205.22) and (550.4,218.7) .. (562.8,217.08) ;
[shift=(564.63,216.75), rotate = 183.71] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(536.36,244.18) .. controls (547.75,243.02) and (559.26,235.92) .. (567.61,220.33) ;
[shift=(568.5,218.6), rotate = 121.91] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(33.43,92) .. controls (150.57,19.43) and (523,-25) .. (578.2,202.2) ;
[shift=(578.2,202.2), rotate = 254.51] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(30.86,111.43) .. controls (136.86,25.71) and (513,-20.73) .. (575,200.6) ;
[shift=(575,200.6), rotate = 252.47] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(30.29,148.57) .. controls (70.33,42.33) and (504,-30) .. (571.97,200.33) ;
[shift=(571.97,200.33), rotate = 251.46] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(273.5,90) .. controls (417.19,22.84) and (515.88,115.44) .. (564.64,201.82) ;
[shift=(565.38,203.13), rotate = 240.32] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(275,115.25) .. controls (401.78,13.76) and (506.78,114.15) .. (562.99,203.82) ;
[shift=(563.83,205.17), rotate = 237.72] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(273,150) .. controls (371.51,3.24) and (503.18,110.91) .. (561.75,206.68) ;
[shift=(562.63,208.13), rotate = 238.26] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(469,339.4) .. controls (456.07,353.13) and (431.84,365.67) .. (346.29,370.53) ;
[shift=(345,370.6), rotate = 355.96] [fill=rgb, 255:red, 0; green, 0; blue, 0   ][line width=0.08]  [draw opacity=0] (7.2,-1.8) – (0,0) – (7.2,1.8) – cycle    ;

(241.36,270.59) .. controls (244.82,272.41) and (249.55,277.14) .. (253.73,282.23) ;

(241.18,268.05) .. controls (245.73,268.41) and (249.36,269.86) .. (253.91,274.05) ;

(240.08,264.36) .. controls (244.62,264.73) and (249.17,265.09) .. (253.71,269.27) ;

(99, 90) node [anchor=north west][inner sep=0.75pt]   [align=left] Time slot $\displaystyle 1$;

(345, 90) node [anchor=north west][inner sep=0.75pt]   [align=left] Time slot $\displaystyle 2$;

(28, 128) node [anchor=north west][inner sep=0.75pt]  [rotate=-90]  $\cdots $;

(270, 128) node [anchor=north west][inner sep=0.75pt]  [rotate=-90]  $\cdots $;

(90,215) node [anchor=north west][inner sep=0.75pt]  [rotate=-90]  $\cdots $;

(210,303) node [anchor=north west][inner sep=0.75pt]  [rotate=-90]  $\cdots $;

(333,215) node [anchor=north west][inner sep=0.75pt]  [rotate=-90]  $\cdots $;

(455,303) node [anchor=north west][inner sep=0.75pt]  [rotate=-90]  $\cdots $;

(493.6,368.2) node [anchor=north west][inner sep=0.75pt]    $\cdots $;

(508,203) node [anchor=north west][inner sep=0.75pt]    $\cdots $;

(17.5, 88) node [anchor=north west][inner sep=0.75pt]  [font=]  $\theta _{1}^{1}$;

(17.5, 111) node [anchor=north west][inner sep=0.75pt]  [font=]  $\theta _{2}^{1}$;

(17.5, 148) node [anchor=north west][inner sep=0.75pt]  [font=]  $\theta _{S}^{1}$;

(57,174.4) node [anchor=north west][inner sep=0.75pt]  [font=]  $\kappa _{1}^{1}$;

(57.4,198) node [anchor=north west][inner sep=0.75pt]  [font=]  $\kappa _{2}^{1}$;

(57,235.2) node [anchor=north west][inner sep=0.75pt]  [font=]  $\kappa _{S}^{1}$;

(103.6,175.8) node [anchor=north west][inner sep=0.75pt]  [font=]  $\rho _{1}^{1}$;

(104,198.4) node [anchor=north west][inner sep=0.75pt]  [font=]  $\rho _{2}^{1}$;

(102.8,234.6) node [anchor=north west][inner sep=0.75pt]  [font=]  $\rho _{S}^{1}$;

(178.8,262.2) node [anchor=north west][inner sep=0.75pt]  [font=]  $\lambda _{1}^{1}$;

(178,285.4) node [anchor=north west][inner sep=0.75pt]  [font=]  $\lambda _{2}^{1}$;

(178.4,322.6) node [anchor=north west][inner sep=0.75pt]  [font=]  $\lambda _{S}^{1}$;

(224.4,261.4) node [anchor=north west][inner sep=0.75pt]  [font=]  $\varepsilon _{1}^{1}$;

(225.2,285) node [anchor=north west][inner sep=0.75pt]  [font=]  $\varepsilon _{2}^{1}$;

(224.4,321.8) node [anchor=north west][inner sep=0.75pt]  [font=]  $\varepsilon _{S}^{1}$;

(258.67,89) node [anchor=north west][inner sep=0.75pt]  [font=]  $\theta _{1}^{2}$;

(259.2,112.07) node [anchor=north west][inner sep=0.75pt]  [font=]  $\theta _{2}^{2}$;

(258.4,148.87) node [anchor=north west][inner sep=0.75pt]  [font=]  $\theta _{S}^{2}$;

(297.6,176.07) node [anchor=north west][inner sep=0.75pt]  [font=]  $\kappa _{1}^{2}$;

(298,199.67) node [anchor=north west][inner sep=0.75pt]  [font=]  $\kappa _{2}^{2}$;

(297.6,236.87) node [anchor=north west][inner sep=0.75pt]  [font=]  $\kappa _{S}^{2}$;

(345.2,176.47) node [anchor=north west][inner sep=0.75pt]  [font=]  $\rho _{1}^{2}$;

(345.6,199.07) node [anchor=north west][inner sep=0.75pt]  [font=]  $\rho _{2}^{2}$;

(344.4,235.27) node [anchor=north west][inner sep=0.75pt]  [font=]  $\rho _{S}^{2}$;

(420.4,262.87) node [anchor=north west][inner sep=0.75pt]  [font=]  $\lambda _{1}^{2}$;

(419.6,286.07) node [anchor=north west][inner sep=0.75pt]  [font=]  $\lambda _{2}^{2}$;

(420,323.27) node [anchor=north west][inner sep=0.75pt]  [font=]  $\lambda _{S}^{2}$;

(466,262.07) node [anchor=north west][inner sep=0.75pt]  [font=]  $\varepsilon _{1}^{2}$;

(466.8,285.67) node [anchor=north west][inner sep=0.75pt]  [font=]  $\varepsilon _{2}^{2}$;

(466,322.47) node [anchor=north west][inner sep=0.75pt]  [font=]  $\varepsilon _{S}^{2}$;

(566.8,204.87) node [anchor=north west][inner sep=0.75pt]  [font=]  $\mu $;

(288,404.07) node [anchor=north west][inner sep=0.75pt]  [font=]  $\delta $;

(330.8,369.8) node [anchor=north west][inner sep=0.75pt]  [font=]  $\tau _{1}$;

(469.2,369) node [anchor=north west][inner sep=0.75pt]  [font=]  $\tau _{2}$;

(518,369.4) node [anchor=north west][inner sep=0.75pt]  [font=]  $\tau _{N}$;

(544.67, 367) node [anchor=north west][inner sep=0.75pt]   [align=left] Tasks;

The graph for which finding the minimum-cost flow gives the global optimum.

Although the CF minimization problem is formulated as ILP in (<ref>), we will demonstrate that the global optimum can be computed in polynomial time. The idea is to construct a graph, along with entities for nodes and arcs, such that the problem maps to finding a minimum-cost flow in the graph. The graph construction, however, is non-trivial. We illustrate the concept in Fig. <ref> and detail the construction below.

§.§ Overview

A minimum-cost flow problem is an optimization problem of finding the cheapest possible way to route flow from supply node(s) to demand node(s) in a directed graph. In the graph, every arc has two attributes: 1) the per-unit flow cost, and 2) flow capacity. A feasible flow solution has to satisfy

* Flow balance constraint: The total incoming flow to a node plus the node's supply, if any, equals the total outgoing flow of the node plus the node's demand, if any.

* Capacity constraint: The flow on every arc does not exceed the arc's capacity.

In our graph shown in Fig <ref>, the green and yellow nodes are nodes with supply and demand, respectively; the other nodes are all transshipment nodes with no supply nor demand. In the graph, green $\theta$-nodes and node $\delta$, red $(\kappa, \rho)$ node pairs, blue $(\lambda, \varepsilon)$ node pairs, and yellow $\tau$-nodes represent the grid, renewable sources, batteries, servers, and tasks, respectively. The flows in the graph represent the amount of energy, and the per-unit cost of an arc is used for accounting for the CF.

Note that the per-unit costs and capacities of arcs default to zero and infinite, respectively, if we do not specify them. Also, we use $(a\rightarrow b)$ to represent the arc from node $a$ to node $b$. As can be seen, the graph consist in a number of sections, and in the following we detail each of them.

§.§ The Entities in a Time Slot

There are $T$ sections indexed by time slot $t$ $(t\in \mathcal{T})$ in the graph. For each of them, there are three types of entities, namely the $\theta$-nodes, $(\kappa, \rho)$ node pairs, and $(\lambda, \varepsilon)$ node pairs.

* Green node $\theta^{t}_{s}$ represents renewable source $s$ in time slot $t$. Its supply in the graph is set to be $R_{st}$, i.e., the amount of energy available from source $s$ in time slot $t$. The meaning of the flows on arcs $(\theta^{t}_{s}\rightarrow \lambda^{t}_{s})$ and $(\theta^{t}_{s}\rightarrow \kappa^{t}_{s})$ are the same as those of the variables $z_{st}$ and $u_{st}$, respectively. By graph construction, the two flows adhere to constraint (<ref>). Note that node $\theta^{t}_{s}$ also connects to the yellow demand node $\mu$ used for receiving the surplus flows (i.e., surplus energy) in the graph to guarantee the feasibility of the minimum-cost flow problem.

* A red node pair $(\kappa^{t}_{s}, \rho^{t}_{s})$ represents battery $s$ in time slot $t$. The capacity of arc $(\kappa^{t}_{s}\rightarrow \rho^{t}_{s})$ is set to be the capacity of battery $s$, i.e., $L$. The flows on arcs $(\delta \rightarrow \kappa^{t}_{s})$, $(\theta^{t}_{s} \rightarrow \kappa^{t}_{s})$, and $(\rho^{t-1}_{s}\rightarrow \kappa^{t}_{s})$ correspond to variables $u_{st}$, $v_{st}$, and $w_{s(t-1)}$, respectively, and they satisfy constraint (<ref>) due to flow balance.

* A blue node pair $(\lambda^{t}_{s}, \varepsilon^{t}_{s})$ represents server $s$ in time slot $t$. The flows on arcs $(\delta \rightarrow \lambda^{t}_{s})$, $(\rho^{t}_{s^\prime} \rightarrow \lambda^{t}_{s})$, and $(\theta^{t}_{s} \rightarrow \lambda^{t}_{s} )$ represent variables $x_{nst}$, $y_{nss^\prime t}$, and $z_{nst}$, respectively. The flows submit to constraint (<ref>) by flow balance. In addition, the capacity of arc $(\lambda^{t}_{s}\rightarrow\varepsilon^{t}_{s})$ is set to be the server capacity $H$, to model constraint (<ref>). Note that the flow through arc $(\rho^{t}_{s^\prime}\rightarrow\lambda^{t}_{s})$ represents that battery $s^\prime$ provides energy to server $s$ in time slot $t$, therefore the per-unit cost of the arc is set to be $\beta_{s^\prime s} I_{st}$, and it accounts for the energy loss in task offloading. Clearly, the total flow cost of these arcs equals (<ref>).

§.§ Battery Level Evolution

Between any two neighboring time slots $t$ and $t+1$ in the graph, there are $S$ arcs, i.e., $(\rho^{t}_{s}\rightarrow\kappa^{t+1}_{s})$, $\forall s\in \mathcal{S}$. The arcs model the evolution of the battery energy between time slots $t$ and $t+1$. The flow on arc $(\rho^{t}_{s}\rightarrow \kappa^{t+1}_{s})$ is the remaining energy in battery $s$ at the end of $t$. By flow balance, the flow on arc $(\rho^{t}_{s}\rightarrow \kappa^{t+1}_{s})$ equals that the flow entering node $\rho^{t}_{s}$ minus the flows representing energy sharing on arcs $(\rho^{t}_{s}\rightarrow \lambda^{t}_{s^\prime})$, $\forall s^\prime \in \mathcal{S}$, and this flow balance implies constraint (<ref>).

§.§ The Grid

The local power grids are merged into a green node $\delta$, and we identify the individual local grids via the arcs to the nodes corresponding to batteries and servers:

* Flow can be sent through arc $(\delta \rightarrow\kappa^{t}_{s})$, and this represents that local grid $s$ charges battery $s$ in time slot $t$. Clearly, its per-unit cost is $I_{st}$ to account for CF in battery charging, and the total flow cost of these arcs equals (<ref>).

* We use the flow through arc $(\delta \rightarrow \lambda^{t}_{s})$ to represent that local grid $s$ provides energy to server $s$ in time slot $t$, and the unit flow cost of arc $(\delta \rightarrow \lambda^{t}_{s})$ is set to be $I_{st}$. The sum of flow costs of these arcs is equivalent to (<ref>).

Arc $(\delta \rightarrow \mu)$ is used for routing the surplus flows from the grid. The flow on the arc represents the amount of grid energy not used by the edge computing network. The amount of supply of node $\delta$ is set to be a sufficiently large value, e.g., $N$.

§.§ The Tasks

In the task section of the graph, a yellow demand node $\tau_n$ represents task $n$. The demand of node $\tau_n$ is one. The arcs between the $\varepsilon$-nodes and $\tau$-nodes are introduced based on the information of the tasks. Specifically, the presence of arc $(\varepsilon^{t}_{s}\rightarrow\tau_{n})$ represents that server $s$ can complete task $n$ in time slot $t$ ($o_n \leq t \leq d_n$). Thus, the flow on this arc represents variable $\pi_{nst}$, and the flow balance constraint for the task node is equivalent to constraint (<ref>).
The per-unit cost of arc $(\varepsilon^{t}_{s}\rightarrow\tau_n)$ is set to be $\alpha_{s_{n}s}I_{s_{n}t}$, and the sum of flow costs on these arcs is equivalent to (<ref>).

§.§ Integrality and Complexity

With the graph constructed, the minimum-cost flow problem can be
solved to the optimum by the network simplex
algorithm[15], and we can obtain the optimal
solution to (<ref>) by tracing the corresponding flows.
Note that the potential difficulty of (<ref>) is that
$\boldsymbol{\pi}$ is binary. Although the flows are not required to
be integer, the integrality theorem of minimum-cost flow problems
guarantees that there always exists an integer optimal solution
<cit.>.  Given an integer optimal
solution, for each task node, only one unit of flow will be routed
from some $\varepsilon$-node as the demand of a task node is one,
i.e., a task will not be split between multiple servers at optimum.

In addition, we have the following theorem with respect to the
complexity of our optimization approach.

CF minimization problem (<ref>) can be solved in polynomial time.

The graph has in total $\mathcal{O}(ST + N)$ nodes and $\mathcal{O}(S^2 + NST)$ arcs, hence the graph constructing can be completed in polynomial time. The complexity of the network simplex algorithm using dynamic trees [16] for solving the problem of the graph is $\mathcal{O}((S^3T + NS^2 T^2+N^2ST)\log(ST + N)\log(STC + NC))$, where $C$ is the maximum cost of any arcs. Hence the conclusion.

§ PERFORMANCE EVALUATION

In this section, we use a 24-hour CI data set of Sweden, Germany, and Poland from [5]; part of this data set is shown in Table <ref>, for performance evaluation. In our simulation, the length of a time slot is an hour. The amount of renewable energy follows a binomial distribution $B(5, 0.5)$ [17] during daytime (7 am to 7 pm), and is zero otherwise. For any task $n$, $o_{n}$, $d_n$ ($o_n \leq d_n$), and $s_n$ all follow a discrete uniform distribution. In addition, we set $\mathcal{S}_n = \mathcal{S}$ $\forall n \in \mathcal{N}$, i.e., a task can be offloaded to any server. The other simulation parameters are specified in Table <ref>. Note that the values of CF in our results are all normalized by $E$.

Simulation Parameters.

Parameter     Value

The number of time slots ($T$)     $24$

The number of servers ($S$)     $3$

The number of tasks ($N$)     $100$

The energy for transferring one task ($\alpha$)     $0.1$

Loss for transferring one energy unit ($\beta$)     $0.2$

float <

float <

float <

[col sep=comma,header=true]
0 ,  7 ,  27464.1
5 ,  7 ,  14408.1
10 ,  7 ,  9417.0
15 ,  7 ,  7024.5
20 ,  7 ,  6030.4
25 ,  7 ,  5610.0
30 ,  7 ,  5333.9
0 ,  8 ,  24431.0
5 ,  8 ,  13741.2
10 ,  8 ,  9063.1
15 ,  8 ,  6639.3
20 ,  8 ,  5808.4
25 ,  8 ,  5314.4
30 ,  8 ,  5094.4
0 ,  9 ,  22348.9
5 ,  9 ,  13279.9
10 ,  9 ,  8967.8
15 ,  9 ,  6499.8
20 ,  9 ,  5657.5
25 ,  9 ,  5182.6
30 ,  9 ,  4924.0
0 ,  10 ,  20266.8
5 ,  10 ,  12849.5
10 ,  10 ,  8885.2
15 ,  10 ,  6434.8
20 ,  10 ,  5536.5
25 ,  10 ,  5050.8
30 ,  10 ,  4829.8
0 ,  11 ,  19292.6
5 ,  11 ,  12518.0
10 ,  11 ,  8802.6
15 ,  11 ,  6402.3
20 ,  11 ,  5443.5
25 ,  11 ,  4975.0
30 ,  11 ,  4819.0
0 ,  12 ,  18799.8
5 ,  12 ,  12376.8
10 ,  12 ,  8720.0
15 ,  12 ,  6402.3
20 ,  12 ,  5378.5
25 ,  12 ,  4910.0
30 ,  12 ,  4808.2
0 ,  13 ,  18452.7
5 ,  13 ,  12268.8
10 ,  13 ,  8637.4
15 ,  13 ,  6402.3
20 ,  13 ,  5313.5
25 ,  13 ,  4877.5
30 ,  13 ,  4797.4

[create on use/sortkey/.style=
create col/assign/.code=
/pgfplots/table/create col/next content
sort key=sortkey,
sort cmp=
iflessthan/.code args=#1#2#3#4
columns/Mtx/.style=string type,
columns/Kind/.style=string type,]

set layers

width=0.5 * ,
height=0.35 * ,
z buffer=none,
xmin=6.5, xmax=13,
ymin=-2, ymax=30,
zmin=0, zmax=56000,
ztick=25000, 50000,
zticklabels=2.5, 5,

extra tick style=grid=major,
zlabel=Total CF,
minor tick num=1,
point meta=explicit,
colormap name=viridis,
scatter/use mapped color=
draw=mapped color,fill=mapped color!60,
execute at begin plot=
let 1=($(axis cs:0,0,1)-(axis cs:0,0,0)$) in

let 1=($(axis cs:1,0,0)-(axis cs:0,0,0)$) in
let 1=($(axis cs:0,1,0)-(axis cs:0,0,0)$) in
3 [visualization depends on=
*z ,
scatter/@pre marker code/.append style=/pgfplots/cube/size z=,
scatter/@pre marker code/.append style=/pgfplots/cube/size x=11.66135pt,
scatter/@pre marker code/.append style=/pgfplots/cube/size y=9.10493pt,
scatter,only marks,
mark=cube*,mark size=5,opacity=1]
table[x expr=x,y expr=y,z
meta expr=-1*x
] ;

The 3D plot shows the total CF with respect to battery capacity $L$ and server capacity $H$.

Fig. <ref> shows the performance results of our proposed scheme with respect to battery capacity $L$ and server capacity $H$. As we can see, there is a dramatic reduction of CF when the battery capacity goes from zero (i.e., no battery) to $5$ units. Thus the importance of battery (and BMS) to create an energy buffer for pursuing low CF is apparent. When $L > 5$, the total CF is hardly improved because such a capacity level can store all the energy required by the tasks. In addition, when the server capacity increases, the total CF decreases as more tasks can be offloaded to servers in low-CI regions.

We are curious about the impact of task offloading and energy sharing, respectively, hence we compare the performance of four schemes:

* S1: This is the proposed scheme considering both task offloading and energy sharing via BMS in the network.

* S2: This scheme allows task offloading but the BMS is disabled, i.e., a battery can only provide energy to its local server.

* S3: This is the opposite to S2, namely energy sharing is enabled, but the tasks can not be offloaded among the servers.

* S4: In the last scheme, task offloading and energy sharing are both disabled; this corresponds to the most basic benchmark for comparison.

In the simulation, we obtain the performance of the four schemes by solving the corresponding minimum-cost flow problems. Figs. <ref> and <ref> show the performance results with respect to battery capacity $L$ and server capacity $H$, where we use w/ and w/o to represent with and without, respectively. Overall, compared with the conventional network (scheme S4), task offloading and energy sharing can help significantly reduce the total CF, up to $83.3\%$ by Fig.<ref> for $L = 5$ and $H = 16$.

scaled y ticks=base 10:-3,

xlabel=The battery capacity $L$,
ylabel=Total CF,
xmin=0, xmax=14,
ymin=0, ymax=22000,

legend pos=north east,

grid style=densely dashed,
tick label style=font=,
label style=font=,
legend style=font=,

[ color=red, mark=square, line width=0.8pt]
( 0 , 11061.0 )
( 1 , 9342.1 )
( 2 , 7706.7 )
( 3 , 6087.9 )
( 4 , 4689.1 )
( 5 , 3379.7 )
( 6 , 2966.0 )
( 7 , 2809.3 )
( 8 , 2674.2 )
( 9 , 2539.1 )
( 10 , 2425.4 )
( 11 , 2311.7 )
( 12 , 2210.0 )
( 13 , 2113.5 )
( 14 , 2078.4 )

[ color=black, mark=triangle, densely dashed, mark options=solid, line width=0.8pt]
( 0 , 11061.0 )
( 1 , 10218.3 )
( 2 , 9378.0 )
( 3 , 8537.7 )
( 4 , 7735.5 )
( 5 , 6933.3 )
( 6 , 6190.4 )
( 7 , 5490.7 )
( 8 , 4812.6 )
( 9 , 4245.1 )
( 10 , 3682.4 )
( 11 , 3119.7 )
( 12 , 2614.0 )
( 13 , 2113.5 )
( 14 , 2078.4 )

[ color=blue, mark=o, dotted, mark options=solid, line width=0.8pt]
( 0 , 19787.0 )
( 1 , 16053.6 )
( 2 , 13501.4 )
( 3 , 11056.8 )
( 4 , 8895.2 )
( 5 , 6815.0 )
( 6 , 5303.2 )
( 7 , 4006.2 )
( 8 , 3679.6 )
( 9 , 3582.6 )
( 10 , 3496.2 )
( 11 , 3413.2 )
( 12 , 3330.2 )
( 13 , 3247.2 )
( 14 , 3188.2 )

[ color=brown, mark=x, dash dot, mark options=solid, line width=0.8pt]
( 0 , 19787.0 )
( 1 , 18807.0 )
( 2 , 17852.0 )
( 3 , 16923.0 )
( 4 , 15994.0 )
( 5 , 15065.0 )
( 6 , 14683.0 )
( 7 , 14301.0 )
( 8 , 13919.0 )
( 9 , 13537.0 )
( 10 , 13155.0 )
( 11 , 12773.0 )
( 12 , 12391.0 )
( 13 , 12009.0 )
( 14 , 11723.0 )

S1: w/ offloading w/ BMS, S2: w/ offloading w/o BMS, S3: w/o offloading w/ BMS, S4: w/o offloading w/o BMS

The total CF as function of the battery capacity $L$ with $H = 10$.

scaled y ticks=base 10:-3,

xlabel=The server capacity $H$,
ylabel=Total CF,
xmin=8, xmax=17,

legend style=at=(0.43, 0.75),anchor=west,

grid style=densely dashed,
tick label style=font=,
label style=font=,
legend style=font=,

[ color=red, mark=square, line width=0.8pt]
( 8 , 4949.3 )
( 9 , 4163.9 )
( 10 , 3379.7 )
( 11 , 3005.4 )
( 12 , 2878.1 )
( 13 , 2767.4 )
( 14 , 2656.7 )
( 15 , 2564.0 )
( 16 , 2528.3 )
( 17 , 2521.1 )

[ color=black, mark=triangle, densely dashed, mark options=solid, line width=0.8pt]
( 8 , 9506.6 )
( 9 , 8014.9 )
( 10 , 6933.3 )
( 11 , 5927.9 )
( 12 , 5033.1 )
( 13 , 4248.9 )
( 14 , 3464.7 )
( 15 , 2766.0 )
( 16 , 2528.3 )
( 17 , 2521.1 )

[ color=blue, mark=o, dotted, mark options=solid, line width=0.8pt]
( 8 , 6818.0 )
( 9 , 6816.0 )
( 10 , 6815.0 )
( 11 , 6815.0 )
( 12 , 6815.0 )
( 13 , 6815.0 )
( 14 , 6815.0 )
( 15 , 6815.0 )
( 16 , 6815.0 )
( 17 , 6815.0 )

[ color=brown, mark=x, dashed, mark options=solid, line width=0.8pt]
( 8 , 15091.0 )
( 9 , 15065.0 )
( 10 , 15065.0 )
( 11 , 15065.0 )
( 12 , 15065.0 )
( 13 , 15065.0 )
( 14 , 15065.0 )
( 15 , 15065.0 )
( 16 , 15065.0 )
( 17 , 15065.0 )

S1: w/ offloading w/ BMS, S2: w/ offloading w/o BMS, S3: w/o offloading w/ BMS, S4: w/o offloading w/o BMS

The total CF as function of the server capacity $H$ with $L = 10$.

In Fig. <ref>, the comparison between S1 and S2 reveals that, when the battery capacity is either very low or very high, energy sharing is of little use. For the former case, it is because there is very little surplus energy available for sharing. For the latter case, the tasks can be offloaded to servers for which the local batteries are charged with low-CI energy. From the results of S1 and S2 in Fig. <ref>, energy sharing is not crucial when the server capacity is large. With high-capacitied servers, the tasks can be offloaded as much as possible to low-CI regions such that we do not need energy sharing for lower CF.

In addition, the curves of S2 and S3 in Fig. <ref> show that task offloading and energy sharing almost give the same effect if the battery capacity is high. This is expected, as the operations of offloading a task to a low-CI region and obtaining some energy from that region achieve the same effect. Thus, joint optimization of offloading and energy sharing is of significance mainly if the server and battery capacities are moderate with respect to the number of tasks.

The performance of S3 and S4 in Fig. <ref> hardly change with increasing server capacity $H$, and this observation shows that optimizing only task scheduling in the time dimension without task offloading leads to a limited reduction of CF. The reason is that the difference of CI in the temporal dimension is typically not so large as that in the spatial dimension.

§ CONCLUSION

We have considered a CF minimization problem for edge computing by joint task offloading and energy sharing. We have formulated the problem as an integer linear programming model. Making the use of the structure of the problem, we have proposed a graph-based reformulation that enables to solve the problem to global optimum in polynomial time. The numerical results demonstrate the large potential of the use of spatial and temporal information of CI for reducing the CF, and joint task offloading and energy sharing does help significantly. Moreover, we can achieve the potential by either improving the energy storage capacity or computing capability. Future work includes, among other things, the extension of non-uniform energy consumption of tasks.

[1]
C. Freitag, M. Berners-Lee, K. Widdicks, B. Knowles, G. Blair, and A. Friday,
“The climate impact of ICT: A review of estimates, trends and
regulations,” 2021. [Online]. Available:

[2]
E. Commission and D.-G. for Communication, Supporting the green
transition : shaping Europe’s digital future.1em plus 0.5em minus
0.4emPublications Office, 2020.

[3]
R. K. Perrons, “How digital technologies can reduce greenhouse gas emissions
in the energy sector's legacy assets,” The Extractive Industries and
Society, vol. 8, no. 4, pp. 101 010 (1–5), 2021.

[4]
Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile
edge computing: The communication perspective,” IEEE communications
surveys & tutorials, vol. 19, no. 4, pp. 2322–2358, 2017.

[5]
Electricity maps. [Online]. Available:

[6]
W. Van Heddeghem, W. Vereecken, D. Colle, M. Pickavet, and P. Demeester,
“Distributed computing for carbon footprint reduction by exploiting
low-footprint energy availability,” Future Generation Computer
Systems, vol. 28, no. 2, pp. 405–414, 2012.

[7]
A. Radovanovic, R. Koningstein, I. Schneider, B. Chen, A. Duarte, B. Roy,
D. Xiao, M. Haridasan, P. Hung, N. Care, S. Talukdar, E. Mullen, K. Smith,
M. Cottman, and W. Cirne, “Carbon-aware computing for datacenters,”
IEEE Transactions on Power Systems, pp. 1–1, 2022.

[8]
C. T. Do, N. H. Tran, C. Pham, M. G. R. Alam, J. H. Son, and C. S. Hong, “A
proximal algorithm for joint resource allocation and minimizing carbon
footprint in geo-distributed fog computing,” in 2015 International
Conference on Information Networking (ICOIN).1em plus 0.5em minus
0.4emIEEE, 2015, pp. 324–329.

[9]
M. Aldossary and H. A. Alharbi, “Towards a green approach for minimizing
carbon emissions in fog-cloud architecture,” IEEE Access, vol. 9, pp.
131 720–131 732, 2021.

[10]
E. Ahvar, S. Ahvar, Z. A. Mann, N. Crespi, R. Glitho, and J. Garcia-Alfaro,
“DECA: A dynamic energy cost and carbon emission-efficient application
placement method for edge clouds,” IEEE Access, vol. 9, pp.
70 192–70 213, 2021.

[11]
C.-S. Yang, C.-C. Huang-Fu, I. Fu et al., “Carbon-neutralized task
scheduling for green computing networks,” arXiv preprint
arXiv:2209.02198, 2022.

[12]
J. Leithon, T. J. Lim, and S. Sun, “Online energy management strategies for
base stations powered by the smart grid,” in 2013 IEEE International
Conference on Smart Grid Communications (SmartGridComm).1em plus
0.5em minus 0.4emIEEE, 2013, pp. 199–204.

[13]
J. Leithon, L. A. Suárez, M. M. Anis, and D. N. K. Jayakody, “Task
scheduling strategies for utility maximization in a renewable-powered iot
node,” IEEE Transactions on Green Communications and Networking,
vol. 4, no. 2, pp. 542–555, 2019.

[14]
L.-L. Li, S.-Y. Wen, M.-L. Tseng, and C.-S. Wang, “Renewable energy
prediction: A novel short-term prediction model of photovoltaic output
power,” Journal of Cleaner Production, vol. 228, pp. 359–375, 2019.

[15]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory,
Algorithms, and Applications.1em plus 0.5em minus 0.4emPrentice-Hall, Inc., 1993.

[16]
R. E. Tarjan, “Dynamic trees as search trees via euler tours, applied to the
network simplex algorithm,” Mathematical Programming, vol. 78, no. 2,
pp. 169–177, 1997.

[17]
C. Coskun, Z. Oktay, and I. Dincer, “Estimation of monthly solar radiation
distribution for solar energy system analysis,” Energy, vol. 36,
no. 2, pp. 1319–1323, 2011.