Survivable Free Space Optical Mesh Network using High-Altitude Platforms

Each HAP carries one down-facing FSO device to communicate with a cluster of ground FSO transceivers. For the ground FSO transceivers, the HAP is called the serving HAP and the FSO device on the HAP is called the serving FSO transceiver. On the same HAP, there may be other FSO transceivers for communicating with other HAPs. These FSO transceivers are called inter-HAP FSO transceivers. The serving FSO transceiver and inter-HAP FSO transceivers on the same HAP should be wired together back-to-back using optical fibers (see Figure 1).

We divide the ground FSO transceivers into clusters, each having a serving HAP. Each ground FSO transceiver communicates with its serving FSO bidirectionally by using two fixed wavelengths for the up and down directions. The wavelengths in the two directions are managed separately because each FSO transceiver has a light source and a light receiver for sending and receiving data independently. The ground FSO devices of the same cluster share access to the common serving FSO transceiver using wavelength devision multiplexing (WDM) technology. Figure 1 illustrates this multiple-access method, where each color represents a wavelength. For simplification, we show only the wavelengths for the up or down direction. Depending on wavelength density of the WDM technique to be used, 32, 64 or more ground FSO transceivers can be served by a single FSO transceiver on HAP.

On inter-HAP links, WDM technique will also be used. Between HAPs data are forwarded on a wavelength-switching basis without wavelength conversion. Data sent from one HAP to the other may travel through multiple HAPs using a continuous wavelength, the so-called lightpath. When the volume of traffic between a pair of HAPs is larger than the capacity of a wavelength, multiple lightpaths may be necessary. These lightpaths do not need to follow the same route.

A ground FSO transceiver may have data to send to different remote ground FSO transceivers. This section explains how the data are switched from end to end. We propose to employ one of two models: IP over WDM and SONET over WDM.

In IP over WDM model, the ground FSO nodes in the same cluster must be assigned IP addresses of the same network. An IP router is installed on each HAP to groom traffic received from the serving FSO transceiver based on destination clusters. Then, the groomed traffic follows different lightpaths between HAPs to reach destination clusters. The end-to-end data are switched as follows:

• •

  At a source ground FSO node, data are encapsulated in IP packets, of which the destination IP addresses are those of the destination ground FSO nodes.

• •

  The packets follow an uplink and arrive at the serving FSO of the source. Here, the IP packets pass through an IP router that directs the packets to different ports dedicated to different destination cluster networks. If the amount of data addressed to a cluster network is larger than the capacity of a wavelength then multiple ports should be used for that cluster.
  The flow of IP packets going out from each router port is regenerated in optical domain using a wavelength and then forwarded to a WDM switch to take a lightpath to get to the serving HAP of the destination cluster.

• •

  At the serving HAP of the destination cluster, IP packets inside each lightpath are DEMUX by the IP router of the HAP according to their destination IP addresses. IP packets heading to the same destination ground FSO node are regenerated in optical domain, using the wavelength assigned to the destination ground FSO node, and transmitted to the ground.

In this switching mechanism, the set of lightpaths between HAPs should be pre-configured beforehand. These lightpaths can be considered as physical links between IP routers. Figure 2 illustrates data switching on a HAP. Port p-HAP-1 is dedicated to receiving traffic for HAP-1 to get to network cluster-1. Port p-HAP-2 receives traffic for HAP-2 to get to network cluster-2. Table 1 shows the IP routing table of the router in Figure 2.

In SONET over WDM model, SONET switches replace IP routers. While IP routers forward data by packet switching basis, SONET switches work on TDM circuit switching basis. Therefore, a circuit should be established for each pair of ground FSO nodes by taking a fixed time slot inside the lightpath between the associated source and destination serving HAPs. The data rate of the time slot corresponds to the volume of requested traffic between the two ground FSOs.

Once one of the above models is employed, the remaining question is setting up lightpaths between HAPs and configuring the IP routers/SONET switches for grooming traffic to lightpaths. In Section 4, we propose algorithms for building the HAP topology and the lightpaths between HAPs, i.e., their paths and wavelengths. Subsequently, IP routers/SONET switches can be easily configured.

On cloudy days, clouds may cut the LoS between a ground FSO node and its serving FSO device. Clouds generally float at an altitude of 10 km. To maintain continuous communication in the network, we propose the following protection mechanism against clouds.

When the LoS between ground FSO nodes and their serving FSO are cut, these ground nodes should forward all their traffic to a nearby alternative HAP, for which the LoS is still clear. Let primary HAP be the serving HAP where data travel in case of no failure whereas the alternative HAP is backup HAP. The backup HAP, after receiving data from a ground FSO node on a wavelength, will simply forward that wavelength to the primary HAP without any processing. At the primary HAP, traffic is handled exactly as it is received directly from the ground, i.e. passing through the IP router and continuing the original lightpaths to the destinations. To receive the backup traffic from the ground, each backup HAP should have a dedicated FSO device that looks at its backup zone. This FSO device is called backup-serving FSO.

Figure 3 illustrates the protection model where zone A is the serving zone of HAP $H_{A}$ and HAP $H_{B}$ backs up for $H_{A}$. Every ground node in the serving zone of $H_{A}$ should forward its traffic to $H_{B}$ whenever its LoS to $H_{A}$ is cut. $H_{B}$ has a backup-serving FSO device for covering zone A.

To implement this model, each ground node should have two light sources and two light detectors oriented toward $H_{A}$ and $H_{B}$. Such an FSO device has been mentioned in [7]. We suggest that the ground nodes transmit two copies of data to both $H_{A}$ and $H_{B}$, and $H_{B}$ always forwards the copies it receives to $H_{A}$. $H_{A}$ chooses to receive the traffic directly from ground nodes or from $H_{B}$ depending on the availability of LoS between $H_{A}$ and its serving zone. This is a 1+1 backup mechanism.

For downstream flows, the backup flows travel along the same paths with the upstream flows but in the reverse direction. When $H_{A}$ has to forward data to its ground FSO nodes, it transmits a copy to $H_{B}$ to relay the copy to the ground FSO nodes. It is the ground node that decides whether to receive from $H_{A}$ or $H_{B}$.

A backup HAP $H_{B}$ must be sufficiently far from its primary HAP $H_{A}$ to avoid that a cloud cuts both links to primary HAP and backup HAP. Based on the altitude of HAPs and clouds, we deduce that the minimum distance between $H_{A}$ and $H_{B}$ should be twice the maximum size of clouds. However, a backup HAP should not be too far from its backup ground FSOs because greater distance causes greater attenuation and air turbulence impact leading to high BER. Therefore, the distance $d(H_{A},H_{B})$ between $H_{A}$ and $H_{B}$ is restricted by:

where $d_{c}$ is the maximum cloud size, $L^{HH}$ is the maximum length of inter-HAP links with BER under the requirement threshold of the current Forward Error Correction techniques.

It is worth noting that if $H_{B}$ backs up $H_{A}$, then topologically, $H_{A}$ could also backup $H_{B}$.

Although the links from a ground node to its primary HAP and backup HAP are not influenced simultaneously by the same cloud, they can still be interrupted by two independent clouds. Let the probability that a link between a ground node and a HAP is cut by clouds be $p_{cut}$, then the probability that both links from a ground node to its primary HAP and backup HAP are cut by two independent clouds is $p_{cut}^{2}$. Consequently, the probability that one of the two links is available for transmission is $1-p_{cut}^{2}$.

The following two cases illustrate the availability offered by the proposed protection mechanism. In the Southern of Europe, the availability of a single link varies between 50% – 85% over a year [16]. Therefore, the proposed protection mechanism allows to increase the joint availability of the links to primary HAP and backup HAP to 75% – 97,75%, which is relatively good. However, in the Northern of Europe, the mean availability of a single link is lower than 40% then joint availability of the two links is still under 64%. More than one slant link may need be considered for improving the joint availability with trade off in cost of backup HAPs and backup FSO transceivers. However, in this research, we focus on single backup slant link only.

To identify a minimum set of HAPs for serving all ground nodes, the ground nodes are organized into clusters, each of which is assigned a serving HAP. There are several constraints to be considered:

• •

  Limited coverage of FSO transceivers on HAPs: ground nodes in a cluster should be inside the coverage diameter $\mathbb{D}$ of its serving FSO. Larger $\mathbb{D}$ allows a serving FSO communicating with more ground nodes leading to fewer HAPs, but requires larger serving FSO apertures thus higher transmit power to maintain the link quality. As a result, HAPs need to recharge more often. The optimal diameter $\mathbb{D}$ should be considered in taking count the trade off between HAP recharging cost and HAP cost. We reserve this optimization problem for a future work as fix $\mathbb{D}$ as a parameter in this research.

• •

  Limited number of wavelengths: The number of ground FSO nodes per cluster is limited by $\mathbb{W}$, the number of wavelengths available according to the WDM technique.

Let us describe the location of a ground FSO node by two coordinates $x$ and $y$ in a 2-dimension Cartesian coordinate system. Assume that all ground FSO nodes are distributed in the quarter where the $x$ and $y$ coordinates are all positive. We propose the following clustering algorithm:

• •

  Step 1: Divide the ground FSO region into non-overlapping bars parallel to the x-axis such that bar indexed $k$ contains the FSO devices with coordinates $\forall y\in[k\mathbb{D}\sqrt{2}\ldots(k+1)\mathbb{D}\sqrt{2}]$. See Figure 4.

• •

  Step 2: We consider bars consecutively, from the index $k=0$ onward. For each bar, the FSO nodes are screened from the smallest to the largest $x$ coordinates:

  • –

    Step 2.1: Find the FSO node, called $F_{1}$, with the smallest coordinate $x$ that has not been clustered.

  • –

    Step 2.2: Find the FSO node, called $F_{2}$, with the largest coordinate $x$ that has not been clustered such that: i) its distance to $F_{1}$ does not exceed $\mathbb{D}\sqrt{2}$, and ii) the number of ground FSO nodes located between $F_{2}$ and $F_{1}$ in the bar does not exceed $\mathbb{W}$.

  • –

    Step 2.3: Create a new cluster including all FSO nodes in the bar between $F_{1}$ and $F_{2}$ inclusively. The serving HAP for this cluster is placed at the coordinates $x=(x_{F_{1}}+x_{F_{2}})/2$ and $y=(k+1/2)\mathbb{D}\sqrt{2}$.

  • –

    Step 2.4: If the cluster is not full, i.e., the number of FSO nodes is still under $\mathbb{W}$, then put into the cluster the FSO nodes that are in the coverage diameter $\mathbb{D}$ of the newly identified serving HAP, even if those nodes do not belong to the current bar. The process is repeated until the cluster is full.

  • –

    Step 2.5: If there are still FSO nodes unclustered in the bar, repeat step 2.1 to create other clusters.

The results of the algorithm are the projected locations of all serving HAPs on the ground and the set of ground FSO nodes served by each HAP. Figure 5 shows the clustering result for the set of ground FSO nodes shown in Figure 4. Each cluster is represented by a circle in which the centroid is the projected location of its serving HAP. Ground FSO nodes are represented by green + symbols in the figure. We can remark that more clusters are formed where the density of the ground FSO nodes is high, while fewer or even no clusters are resulted where the density of ground FSO nodes is low.

In this step, we find a backup HAP for each serving HAP. Assume the maximum cloud size is $d_{c}$, the backup HAP should be at a distance of at least $2\times d_{c}$ from the primary one.

Our idea is that, starting from the set of HAPs found from the clustering step, we match them in pairs so that HAPs in a pair backup each other. The matching problem can be solved using Edmonds’ Blossom algorithm [19] which finds a maximum cardinality matching in a graph. Applying to our problem, the graph contains all HAPs as vertices and edges are inter-HAP links whose lengths are greater than $2\times d_{c}$ but smaller than $L^{HH}$, the maximum allowable length for an inter-HAP link. The maximum matching provides the largest number of pairs of primary and backup HAPs. If the algorithm fails to find a matching for a HAP, we add a new HAP as the backup HAP for it. The newly added backup HAP must be at $2\times d_{c}$ distance from the primary HAP.

After matching backup, a number of wavelengths need to be reserved on the link between a primary HAP and its backup HAP for carrying backup upstream and downstream traffic. In Figure 3, when $H_{B}$ backs up $H_{A}$, the number of wavelengths to be reserved on link $H_{B}\rightarrow H_{A}$ is equivalent to the number of ground FSO nodes served by $H_{A}$ because the upstream traffic from a ground FSO node travels on a single wavelength over link $H_{B}\rightarrow H_{A}$. Similarly, the same number of wavelengths must be reserved on the opposite link $H_{A}\rightarrow H_{B}$ for downstream traffic.

Since $H_{A}$ also backs up $H_{B}$, a number additional wavelengths equivalent to the number of ground FSO nodes served by $H_{B}$ should be reserved on the links $H_{A}\rightarrow H_{B}$ and $H_{B}\rightarrow H_{A}$. As a result, the link $(H_{A},H_{B})$ can accommodate backup traffic for both $H_{A}$ and $H_{B}$ only if the total number of ground FSO nodes of $H_{A}$ and $H_{B}$ does not exceed $\mathbb{W}$.

Once the locations of primary HAPs are identified and backup HAPs have been assigned to them, the remaining issue is to determine the inter-HAP links to be deployed and the lightpaths to be setup between HAPs in order to accommodate all traffic requests. Since the wavelengths dedicated to backup traffic are reserved during the backup matching step, the remaining traffic to be accommodated is the primary traffic. The amount of primary traffic to be sent between two HAPs is the sum of the demanded bandwidth between their ground FSO nodes. Therefore, the number of lightpaths to be setup between a pair of HAPs is the ratio of the demanded bandwidth between the HAPs and the bit rate $r^{max}$ of a wavelength. The topology design problem is stated as follows:
Given:

• •

  Locations of HAPs obtained from the clustering step and those added in the backup matching step.

• •

  $\mathbb{M}^{HAP}$: set of traffic demands between pairs of HAPs. Each demand is represented by a tuple $(s,d,n)$, where $s$, $d$ and $n$ are, respectively, the source HAP, destination HAP and number of lightpaths needed to carry traffic from $s$ to $d$.

• •

  Some parameters as given in Table 2.

Constraints:

• •

  All end-to-end lightpaths should have BER under $\delta$.

• •

  Wavelength continuity constraint along each lightpath.

Output:

• •

  We need to identify the necessary inter-HAP links and lightpaths for carrying all traffic in $\mathbb{M}^{HAP}$ such that the total number of FSO transceivers to be carried on HAPs is minimized.

The idea of the proposed algorithm is that: from a set of possible inter-HAP links, we find routes for demands in $\mathbb{M}^{HAP}$one by one, and incorporate the links on the routes in the topology. The links already included in the topology are assigned small weights so that they will be prioritized in subsequent demands, thus new links are involved only when there is no possible route within the current topology.

Wavelengths are assigned to routes based on the least used strategy. The least used wavelength is defined as the wavelength that carries traffic on the smallest number of inter-HAP links.

Below are some notations used in the algorithm:

• •

  $G_{w}$ denotes the directed graph, where vertices represent HAPs, and arcs represent all possible directional inter-HAP links with wavelength $w$ available.

• •

  $nFreeW(e)$ denotes the number of free wavelengths of directional link $e$.

• •

  $c_{e}$ denotes the weight assigned to directional link $e$,

  $$c_{e}=\left\{\begin{array}[]{ll}100&\mbox{if }e\mbox{ has never been used}\\ 1-\frac{nFreeW(e)}{\mathbb{W}}&\mbox{otherwise}\\ \end{array}\right.$$

  (3)

• •

  $T$ denotes the topology of the HAP network during construction. Initially, $T$ contains all bidirectional inter-HAP links connecting primary HAPs and their backup HAPs. On these links, wavelengths for backup purpose were marked as used.

• •

  $C(u)$ denotes the number of FSO devices to be on HAP $u$ according to topology $T$. $C(u)$ includes all serving FSO devices of HAP $u$ and one FSO device as the endpoint for each bidirectional inter-HAP link adjacent to $u$.

Algorithm 1 shows the pseudo-code of the proposed algorithm. For each demand $(s,d,n)\in$ $\mathbb{M}^{HAP}$, we find $n$ lightpaths from $s$ to $d$, each one uses a single wavelength and possibly take a individual route. The main steps are explained bellow:

• •

  Step 1 (lines 13–23 of Algorithm 1): Assume that the current least used wavelength is $w$, we find the weighted shortest path from $s$ to $d$ in $G_{w}$ using Algorithm 2. Algorithm 2, proposed in [18], is a modified Dijkstra algorithm, which finds the shortest path having end-to-end BER under threshold $\delta$. The found path is called $p$. Each arc of $p$, that is not in $T$ yet, is checked to see if both HAPs adjacent to it having free payload capacity for installing an additional FSO device for the arc. If at least one HAP violates the constraint, the arc is removed from $G_{w}$, and another path will be sought using Algorithm 2 again. This step could be repeated until no violation is found, or no path is found.

• •

  Step 2: If no path is found on $G_{w}$ for the current demand, then try to find a path on $G_{j}$, where $j$ is the next least used wavelength and so on (line 24). When all wavelengths have been screened but no path is found, this demand is rejected (lines 46–47).

• •

  Step 3: When no violation is found, the path is good for the current demand, wavelengths are assigned to it to make lightpaths:

  • –

    The new arcs of $p$ are added to $T$ and the first lightpath for the demand $(s,d,n)$ is recorded as using wavelength $w$ along path $p$ (lines 26–30).

  • –

    If the number of requested lightpaths $n>1$, the remaining number of lightpaths to be created is $remain-LP=n-1$. We try to make the remaining lightpaths by using always path $p$ but other wavelengths starting from the least used wavelength available first (lines 31–38).

  • –

    If there are still not enough available wavelengths to route the entire demand over $p$, the un-routed lightpaths should follow a different path. We consider the remaining part of the current demand as a new one with parameters $(s,d,remain-LP)$ and add it to $\mathbb{M}^{HAP}$for later handling (lines 39–40).

At the end of the algorithm, we obtain the topology $T$ for the HAP network and all lightpaths for the accepted demands in $\mathbb{M}^{HAP}$.

Figure 6 shows the topology of the HAP network designed by the proposed algorithm for the test case shown in Figure 5. Blue dots are HAPs providing backup function, and blue dashed lines are inter-HAP links between a pair of primary and backup HAPs.

Figure 7 shows the number of HAPs as a function of the number of ground nodes. This shows that protection requires at most one more HAP in all test cases. The reason is that: if HAPs still have free payload for installing backup serving FSO devices, serving HAPs of different clusters backup each other. The additional HAP is only involved when the number of clusters is impaired. Thus, the protection does not lead to a higher cost of HAPs if the HAPs are not too loaded prior protection.

Figure 8 shows the total number of FSO devices to be installed on HAPs with and without protection. Evidently, cases with protection require additional FSO devices to serve ground nodes in the protected zones and to connect the primary and backup HAPs. Nonetheless, the total number of FSO devices to be deployed on HAPs increases only by 5%–12% owing to protection.

Figure 9 shows the average number of FSO devices that a HAP carries with and without protection. We observe that, on average, each HAP has to carry from 0.45–0.95 more FSO devices for protection purpose.

Figure 10 shows the number of inter-HAP links when the number of ground nodes increases. Since traffic demands were generated between all ground nodes, the volume of traffic increases proportionally with the number of ground nodes. As a result, more inter-HAP links are involved in networks with larger number of ground nodes.

Counter intuition, the statistics demonstrate that the topology with protection generally uses fewer links than the topology without protection. The difference becomes clearer when the number of ground nodes increases. We believe that this phenomenon is due to the characteristics of the proposed algorithm. In the backup matching step, a number of inter-HAP links connecting pairs of primary and backup HAPs are included in the initial topology $T$. Consequently, the topology design algorithm frequently uses these links, resulting in fewer added links than in the no-protection scenario. We believe that by modifying the topology design algorithm, it is possible to achieve a topology without protection with fewer links.

The analysis of link occupation confirms that links are exploited more intensively in topologies with protection. We define link occupation as the ratio between the number of wavelengths used and the total number of wavelengths of the entire network:

Coefficient 2 in the denominator is introduced because a link is bidirectional, and wavelengths are counted separately in opposite directions.

Figure 11 shows that link occupation in topology with protection is clearly higher than link occupation in topology without protection mostly when the number of ground FSO nodes increases.

We evaluated the impact of protection on the quantity of wavelength resources in the network topology. Let link-wavelength be a wavelength of a link. The number of link-wavelengths increases when more wavelengths are used in many links. We calculated the total number of link-wavelengths used in all inter-HAP links of the topologies with and without protection for each test case. Figure 12 shows the percentage of additional link-wavelengths used for protection. The topologies with protection use from 8% to 40% more link-wavelengths than those without protection. The amount of additional link-wavelengths is modest because in the case with protection, demands travel over only one more link (between the backup and primary HAPs) compared to the case without protection.