Link Design for Wireless Optical Communication Network based on Ant Colony Algorithm

1. Introduction

CURRENT key initiatives in deep-space laser communication are treated in terms of historical context, contemporary trends, and prospects for the future. Deep-space communication is the basis and support for deep-space exploration. It is not only the approach of information exchange between deep-space and earth, but also the important guarantee for the normal operation of the deep-space exploration. Thus, deep-space communication plays a very important role in deep-space exploration project [1]. Compared with traditional microwave communication, laser communication has many advantages such as large-capacity, good confidentiality, lightweight, miniaturization and so on [2]. Laser communication has been recognized as one of the most promising transmission technology of deep-space communication systems. With the maturation of space laser communication

technologies and the development of deep-space exploration technologies, DSON is expected to become an important foundation and inevitable development trend of future deep-space communication. However, because of laser communication’s characteristics of long-distance and line-of-sight transmission, and the characteristic of probes with limited energy supply, DSON will face the challenges of connectivity and routing. In order to minimize the overhead and look for the best transmission path, designing an efficient, reliable and flexible routing algorithm in DSON has been always a big challenge for the research.

The main challenges that affect routing in deep-space network include [3]: Long and variable propagation delay, intermittent connectivity, high bit error rate, energy constraints, link asymmetry, and so on. Most of these characteristics are unique to the space communication paradigm. In addition, a deep-space network is also a special type of delay-tolerant networks (DTN) [4], where the continuous end-to-end connectivity cannot be assumed. Reference [5] assumed that the connectivity patterns of network were known, and formulated the DTN routing problem based on different knowledge about the network topology. However, the proposed algorithm required error-free communications, and no effective solutions were given when unpredictable link failures occurred.

To our knowledge, in the routing area of DSON, there is only little work to count in the literature. Reference [6] proposed a congestion-aware routing scheme in interplanetary networks and formulated an optimization problem for nexthop selection via multi attribute decision makings. However, the routing strategy did not take account of the benefits brought by transmitted energy reservations because of the finite energy of nodes in interplanetary networks. Reference [7] proposed a space gateway routing framework through different autonomous regions in ad hoc space networks based on interplanetary backbone network. However, this scheme cannot be effective in intermittently connected network topologies. Reference [8] presented a buffer-aware probabilistic routing protocol for interplanetary ad hoc network, which considered the buffer size of neighbor nodes and the past history of encounters with other nodes while taking a routing decision. However, it is not hard to see that the bandwidth available and energy efficiency during transfer were not evaluated. In [9], it investigated a joint cross-layer optimized routing and dynamic energy allocation for intermittently connected deepspace backbone layer in interplanetary link. But this scheme was based on predictable contacts.

This paper studies on the routing optimization of DSON. According to the characteristics of DSON, first of all, this paper presents a DSON architecture based on FWMN to build a multi-hop DSON. In 1991, an Italian scholar M. Dorigo proposed ant colony algorithm, which is a new bionic optimization algorithm and simulated evolutionary algorithm [10]. Because of its characteristics of positive feedback, distributed computation and greedy heuristic search, it is used to find optimal path. Due to the similarity between the optimization process and the solution of traveling salesman problem, the optimal solution of TSP with NP complexity (non deterministic polynomialcompletion) is obtained [11]. Then, this paper proposes DSON routing algorithm based on TACA to solve the unidirectional links problem existing in the network and find an optimal path. In addition, in order to control the energy consumption speed of nodes and prevent premature death of nodes, we put the node energy as the routing factor in the routing, so as to reduce the possibility of unidirectional links and improve the network survivability. Besides, to speed up the ant colony algorithm convergence rate, this paper improves the ant colony algorithm pheromone update procedure by reserving the node pheromone for the subsequent path finding.

The remainder of this paper is organized as follows. Section II presents the problem statement. In Section III, we propose the algorithm of RA-ACA for DSON. Simulation results are given and discussed in Section IV. Finally, Section V concludes this paper.

II. PROBLEM FORMULATION

A. Structure of DSON

DSON consists of a set of stable relay nodes with high availability and high capacity, which provides data link between long distance communication nodes including direct links or multi-hop links. These relay nodes send navigation information and telemeter control information for the detectors, space stations, space shuttles and so on. Besides, the relay nodes also store and forward scientific data [12]. Fig. 1 shows a simple structure of DSON, it includes the satellites of the Moon, Mars, and Earth, as well as the satellites positioning on Lagrange point. As shown in Fig. 1, there are communication links among the whole nodes, which constitute the DSON. Through the DSON, deep-space equipments can transmit data to earth stations by relay or multi-hop manner, and avoid transmission interferences by obstacles. Thus the losses caused by long distance transmission will be reduced. The topology of deep space optical network is changing in real time. Deep space environment is complex, and with the increase of deep space exploration equipment. The problem of obstacles often leads to the existence of a large number of unidirectional optical links or asymmetric links. At this time, the two nodes can only communicate in one direction.

There are two routing strategies for DSON [13]. One routing strategy is a dynamic routing based on actual network communication state, which feels out the link performance by communication tests. Then according to the shortest delay, the strongest signal and maximum visual time, the optimal path will be found by the fewest hops and other criteria. The other routing strategy primarily utilizes the periodic repetition

of satellite motion, and then the time is divided into a lot of segments. The inter satellite links remain relatively unchanged, therefore, the routing table within different time segments can be regularly updated.

In this paper, we will adopt the second routing strategy. The topology structure of DSON is actually dynamically changing with the time, but the change is periodic and regular. Thus the DSON topology can be regarded as changeless in a certain time segment. The integrity of DSON should be a discrete combination with a plurality of time segments, and DSON can be considered as a discrete dynamic network [14]. In this paper, we will design the network structure in a single time segment, which is a FWMN, and this design can be referenced for all the time segments. The FWMN is a distributed network topology structure, and has high reliability and fault tolerance. In this network topology, each node can be connected to other nodes, and each node also has redundant paths, as shown in Fig. 1. The Earth can be used as a gateway, which can connect other network outside the DSON, such as Internet. The user nodes can be deep-space probes and exploration satellites, which constitute the FWMN. Each node can realize the nonline- of-sight connection with Earth by multi-hop, and guarantee the long distance transmission of information. Because the FWMN nodes are much simpler than other wireless mesh network (WMN), this is good for the design of deep-space probes.

Compared with traditional wireless access technology, the FWMN also has the following characteristics [15]: 1) Multihop wireless network. The multi-hop WMN architecture has much shorter wireless link, smaller transmission power and node interference. 2) High coverage rate. In the FWMN, due to the shorter node distance, each node can establish a connection only with lower transmission power, meanwhile, the shorter node distance means that the possibility of the obstacle in the transmission is reduced, which is convenient to adopt lineof- sight transmission. 3) High reliability and stable topology structure. Each user node will be able to connect other gateway nodes by multiple paths. When a gateway or user node has failed, the user node can access network by other nodes. 4) Supporting multiple types of access methods.

B. Problem of Unidirectional Links

One of the main characteristics of laser communication is line-of-sight communication, that is, no obstacles between source and destination. Hidden terminals and obstacles will cause a large number of unidirectional links, thus, in DSON, not only bidirectional links but also unidirectional links arise. One of major causes of such links is different transmission ranges of DSON nodes as illustrated in Fig. 2 [16]. We can see that node A and B have different transmission ranges. Node A on the one end of a unidirectional link is called a downstream node, which receives packets from the other but cannot send ones back. Node B on the other end of unidirectional link is called upstream node. Most of routing protocols designed for DSON work with the assumption that all nodes in a network have the same transmission range or all wireless links are bidirectional. However, this assumption does not always hold. Once the unidirectional links exist, the performance of these route protocols will be degraded.

The reasons for unidirectional links in DSON are as follows: 1) Different DSON nodes have different transmission abilities, thus the transmission ranges are always different. 2) The existence of obstacles, which will cause the link interruption. 3) The influence of background noise, for example, the Sun outage phenomenon occurs when the Sun, the Earth and a satellite are aligned, and it is an interruption in satellite signals caused by interference from solar radiation.

At present, the wireless network routing algorithms for solving unidirectional links include black list method, HELLO method and reverse path search method [17]. The unidirectional links will be shielded according to above methods, thus only bidirectional links exist in the network. This method is effective to a certain extent. However, when a node only connects the network via the unidirectional links, above methods will lead to the node losing connection with the entire network. In addition, when the performance of unidirectional links is better than bidirectional links, using unidirectional links can save network source. Therefore, we will make full use of unidirectional links, and effectively utilize the network resource.

C. Problem of Node Energy Consumption

The energy of spacecrafts is selected according to mission requirements and the development level of space energy, thus all kinds of spacecrafts can choose different energy [18], [19]. Orbiting satellites and short lifetime satellites always use chemical cell or battery group, while most of long lifetime satellites take solar array. However, the solar of spacecraft is inversely proportional to the square of distance from the sun. Thus, the light intensity directly affects the design of detector energy system. The exploration of deep-space is away from the sun, if using solar energy like the satellites, deepspace probes need to carry much more solar panels. This is difficult for the deep-space probes with limited load. When the light intensity is poor, the solar array cannot be used. Such as the exploration of Saturn system, the using of solar is impossible. In addition to the distance, deep-space probes may experience long shadow and long irradiation during the flight, thus, the radiation change is rather large. Therefore, deep-space probes are limited by weight, volume, environment and other factors, which can adopt nuclear energy. Compared with solar energy, nuclear energy will be not affected by solar irradiation with longer work lifetime. Unluckily, when the limited nuclear energy is consumed over, the work ability of deep-space probes will be lost. Therefore, the energy of deepspace probes is rather limited, it is important to save the energy and extend the lifetime of probes.

Limited energy will affect the network lifetime, transmission delay and transmission cost without controlling the energy consumption speed. This is not conducive to the network connectivity. The influences of fast energy consumption speed for DSON are as follows: 1) It will lead to the premature death of nodes, and the probes may be unable to complete the assigned task. Then the probes will be early rejected. 2) Network performances will be influenced. When the death nodes occur in the process of path finding, it needs to find another alternative path. This will increase the transmission delay and transmission cost, resulting in the performance reduction of network. The traditional method to extend the service lifetime of deep-space detectors is a rational design of energy supply system, so as to improve use efficiency and conversion efficiency, and realize rational distribution of energy by using intelligent management technology. Nevertheless, these are the improvements of probes themselves, and they do not consider how to control node energy consumption speed in the process of sending and receiving information. Hence, in this paper, we will research the energy consumption of the nodes. In the routing, we will also take node energy as a routing factor besides considering minimum delay. Accordingly, the network performance can be effectively improved, and the lifetime of DSON will be increased.

III. ALGORITHM DESCRIPTION

A. Notation

[TeX:] $$G\langle V, E\rangle$$ Wireless network, V and E denote node set and link set, respectively. [TeX:] $$s \in V$$ represents source node set, and [TeX:] $$D \subseteq\{V-\{s\}\}$$ is destination node set.

[TeX:] $$\operatorname{tabu}_{k}:$$ Tabu list, which saves the nodes already visited by kth ant.

[TeX:] $$d_{i j}:$$ Distance between node i and node j.

i,j: Index of node, [TeX:] $$i, j \in\{1,2, \cdots, n\}.$$

[TeX:] $$b_{i}(t):$$ Number of ants on node i at time t.

[TeX:] $$\tau_{i j}(t):$$ Amount of pheromone deposited on edge (i, j) at time t.

[TeX:] $$\eta_{i j}(t):$$ Heuristic function, which can be also denoted the visibility of edge (i, j).

[TeX:] $$\alpha:$$ A parameter to control the influence of [TeX:] $$\tau_{i j}(t).$$

[TeX:] $$\beta:$$ A parameter to control the influence of [TeX:] $$\eta_{i j}(t).$$

[TeX:] $$p_{i j}^{k}(t):$$ Transition probability for the kth ant from node i to node j at time t.

M: Number of each wave ants.

K: Number of iterations.

k: The kth ant.

[TeX:] $$Q$$: Strength coefficient of pheromone.

[TeX:] $$\rho:$$ Evaporation coefficient of pheromone.

power (n): Node energy.

delay (n): Delay function.

delay jitter (e): Delay jitter function, e denotes any link.

bandwidth (e): Bandwidth function, e denotes any link.

cost (e): Cost function, e denotes any link.

B: Bandwidth between node i and node j.

C: Cost between node i and node j.

D: Delay between node i and node j.

PL: Packet loss rate of node.

-Constraints of RA-ACA algorithm

(1) Bandwidth constraint: [TeX:] $$\text { bandwidth }\left(P_{T}(s, d)\right) \geq B$$

(2) Delay constraint: [TeX:] $$\operatorname{delay}\left(P_{T}(s, d)\right) \leq D$$

(3) Delay jitter constraint: [TeX:] $$\text { delay_jitter }\left(P_{T}(s, d)\right) \leq D J$$

(4) Packet loss rate constraint: [TeX:] $$\text { packet_loss }\left(P_{T}(s, d)\right) \leq P L$$

(5) Energy constraint: Selecting the larger power (n) in the optional next hop nodes where B, D, DJ, and PL are the bandwidth, delay, delay jitter and packet loss rate of path [TeX:] $$P_{T}$$ (s, d), respectively. In the DSON, we will use (d, dj, b, c) to denote the characteristics of each edge, and (d, dj, pl, c, p) represents the characteristics of each node. d, dj, pl, c, and p are the variables of delay, delay jitter, packet loss rate, cost, and energy, respectively.

-Objective

In the RA-ACA approach, our objective is to minimize the total cost of path [TeX:] $$P_{T}$$ (s, d). We can represent the objective as follows:

B. Principle and Mathematical Model of RA-ACA for DSON

This paper will combine the characteristics of the deepspace laser communication on the basis of TACA, and propose the RA-ACA for DSON. Compared with TACA, this algorithm will be improved in the following aspects: 1) We will make full use of unidirectional links resources and improve the performance of DSON. 2) In order to control the energy consumption speed of nodes and prevent premature death of nodes, we put the node energy as the routing factor in the route, thus the lifetime of the whole network will be increased. 3) We will reserve the node pheromone for the subsequent path finding in order to enhance the convergence speed.

Because of the group intelligent characteristics of ants, the ants can always find the optimal path between the nest and the presence of food. Ant colony optimization algorithm has been demonstrated successfully in solving hard combinatorial optimization problems effectively. It is inspired by real ant colonies in the nature, who can find the shortest path from the nest to food by depositing a chemical substance called pheromone on the ground. Some novel strategies, positive feedback, distributed computation and constructive greediness for example, are adopted in ant colony optimization algorithm. At the initial time of path finding, the distribution of pheromone of each path is equal, i.e., [TeX:] $$\tau_{i j}(0)=\mathrm{C}$$ (C is a constant). In the process of path finding, the shift direction of the kth ant will be decided by pheromone function, and the kth ant can only choose one of the target nodes at time t. Thus the defined transition probability from node i to node j for the kth ant is given by [20]:

where [TeX:] $$\text { allowed }_{k}=\left\{V-t^{2 b} u_{k}\right\}$$ represents the node that ant k is allowed to select in the next step. V denotes the set of neighbor nodes. [TeX:] $$\alpha \text { and } \beta$$ are parameters that control the relative importance of trail versus visibility. The greater indicates that the ants tend to choose the path of other ants. That is to say the cooperation among ants is much stronger. Similarly, is the importance of visibility, which represents relative important degree in guiding the ant colony search for heuristic information. When is much greater, the state transition probability will be close to the greedy rule. The reserved pheromones will gradually disappear with the passage of time. The ants will complete a cycle after n moments, and the pheromone on each path should be adjusted according to the following formulae:

where [TeX:] $$\rho$$ is the evaporation coefficient of pheromone, and [TeX:] $$1-\rho$$ denotes the pheromone residue factor. The coefficient [TeX:] $$\rho$$ must be set to a value less than 1 to avoid unlimited accumulation of trail. [TeX:] $$L_{k}$$ is the tour length of the kth ant. [TeX:] $$\Delta \tau_{i j}$$ is the pheromone increment on the edge (i, j). We set the pheromone increment [TeX:] $$\Delta \tau_{i j}$$ is 0 at the initial time. In addition, [TeX:] $$\tau_{i j}^{k}$$ indicates the pheromone strength on the path ij released by kth ant in this cycle. Equation (5) is used to solve the pheromone increment in Ant-Cycle model, and Q is the intensity ofpheromone, which is the total amount of pheromone released on the path of ants in a cycle.We add node energy P (j) in (6), which represents the node energy of next hop. Due to bigger P (j) and much more pheromone on the path ij, [TeX:] $$P_{i j}^{k}(t)$$ will be much larger. In this paper, pheromone on the path will be updated through above formulae, and the transition probability will be changed.

C. Procedure of RA-ACA for DSON

In the DSON, laser communication is line-of-sight communication, that is, no obstacles between the source and destination. Obstacles and background noise will cause the link interruption, and lead to the unidirectional links existing in the network. The unidirectional links will be shielded according to traditional routing algorithm, thus this will result in the waste of network resources. In this paper, we will make full use of unidirectional links and propose the RA-ACA for DSON. The ants can be viewed as mobile agents, i.e., control message, which can be divided into three categories. They are forward ants (Fants), backward ants (Bants) and broadcast backward ants (BBants). The route will be determined by the interactive information between ant agents. Then, the energy of deepspace nodes is limited. If we don’t consider the node energy, the deep nodes will prematurely die, thus the nodes may be unable to complete the assigned task. Besides, the lifetime of DSON may be reduced. Therefore, we will choose larger node energy as next hop according to transition probability formula, and avoid selecting the node with smaller energy, so that to prolong the lifetime of the whole network. At last, the ant colony algorithm is an iterative process, whose complexity is much higher. When we solve the optimization problem by ant colony algorithm, most of calculation time will be used for the construction of solutions. Thus, the speed of search optimal solution may be slower than other algorithms. In order to improve the average convergence speed of optimal path, the links that don’t meet bandwidth, packet loss rate and delay conditions will be removed before the routing. Hence, the number of search paths will be decreased. Then, we will reserve the node pheromone for the subsequent path finding, so as to enhance the convergence speed. The specific steps of RA-ACA for DSON are as follows:

Step 1: Initialize DSON

Each node maintains a pheromone table, which can be used to record the transition probability to each neighbor node. Every edge (i, j) sets an initial pheromone value [TeX:] $$\tau_{i j}(t)=c$$ and [TeX:] $$\Delta \tau_{i j}=0.$$ The constraint conditions that bandwidth and packet loss rate can be set. In addition, set the iteration number and the source node set. Place the M ants on the source node;

Step 2: Delete the links and nodes that does not meet the constraint conditions of bandwidth and packet loss rate;

Step 3: Place the source node in the [TeX:] $$\operatorname{tabu}_{k},$$ and send out M ants from source node for path finding;

Step 4: Compute the transition probability [TeX:] $$P_{i j}$$ according to (2), each Fant chooses the next hop according to [TeX:] $$P_{i j},$$ and place this node in [TeX:] $$\text { tabu }$$ Repeat this step until it finds the destination or there is no next hop;

Step 5: All Fants complete a cycle after time [TeX:] $$\Delta t.$$ Judging that each Fant whether finds the destination. The Fants that find destination will generate a Bant;

Step 6: According to pheromone table, each Fant finds out whether there is a path to the front hop node. If the

path exists, algorithm performs the unicast Bants along the path. Meanwhile, algorithm updates the transition probability according to the (2), (3), (4), and (6). Otherwise, algorithm generates and broadcasts BBants to search the last hop of the node. Then, algorithm updates pheromone table according to the information of Fants. This step will be repeated until it reaches the source node;

Step 7: Clear [TeX:] $$\text { tabu }$$ and return step 3 until the completion of K iterations;

Step 8: Save the pheromone on the path which has been found destination node, and then initialize other parameters;

Step 9: If some destination nodes also cannot be found, algorithm returns to step 2, until all the destination nodes will be found;

Step 10: Output the results.

IV. SIMULATION RESULTS

A. Simulation Settings

According to the structure of DSON in Fig. 1, we will abstract the corresponding simulation topology for DSON as shown in Fig. 3. Assuming that unidirectional link exists between node 1 and node 3. The simulation parameters are [TeX:] $$\mathrm{B}=70 \text { Mbps, } \mathrm{D}=50 \mathrm{~s}, \mathrm{DJ}=12 \mathrm{~s}, \mathrm{PL}=0.001, \alpha=1, \beta=1, \rho=0.5, \mathrm{Q}=100, \mathrm{~K}=20, p \in[1,10] \text {, and } M=10 \text {. }$$ The source node is s = 1 and the set of destination nodes is 5, 6.

B. Results and Analysis

According to network topology in Fig. 3, we examine the performance of RA-ACA for DSON about the unidirectional links. In the topology, we can see that there is a unidirectional link between node 1 and node 3. Node 1 is the source node and destination is node 6. Thus, we separately simulate 25 times for the RA-ACA for DSON and TACA. The results are shown in Table I.

As shown in Table I, the number of successful convergence with TACA is 20 times, but in RA-ACA, the number of successful convergence reaches 24 times. Compared with TACA, the number of successful convergence for RA-ACA

has been improved 16%. When [TeX:] $$k \leq 10,$$ we can see that the number of convergence is 11 in TACA, and the RAACA is 22 times. The latter is twice as much as that of TACA. Meanwhile, from the iterative mean of successful convergence, it can be seen that RA-ACA is lower than TACA as much as 4.18 times. Therefore, the performances of successful convergence number and convergence speed for RA-ACA are better than TACA. In addition, we can see that the path delay average of RA-ACA reduces 9.19 s compared with TACA. Moreover, when the delay is less than 30 s, the number of convergence for TACA is 12, while the RA-ACA is 22. Similarly, the latter is approximately twice as much as that of TACA. In summary, the performance of RA-ACA is better than TACA. Because the RA-ACA makes full use of unidirectional links, the total delay of convergence path can be lower than TACA. Fig. 4 is the delay of convergence path with different iterations. We can see that the delay of RA-ACA is significantly lower than that of TACA. The convergence delay of RA-ACA is about 8s lower than that of TACA. Besides, the convergence speed of RA-ACA is obviously faster than TACA.

In addition, in order to accelerate the convergence speed, we consider to reserve the node pheromone for subsequent path finding. Figs. 7, 8, and 9 are the convergence speed of delay, delay jitter and cost with reserving the node pheromone, respectively. We can see that the convergence speed is much faster than without reserving node pheromone. For example, in Fig. 7, the RA-ACA scheme needs four iterations before convergence without reserving node pheromone. When RA-ACA scheme reserves node pheromone, the delay curve with two

iterations will converge. The convergence speed is increased by 50%. Similarly, convergence speeds of delay jitter curve in Fig. 8 and cost curve in Fig. 9 are both increased by 50%. In this paper, RA-ACA for DSON can control the node energy consumption speed. Because it will choose the larger energy of node as the next hop, the path with sufficient energy can be found. This scheme can rationally allocate the energy and prevent premature death of nodes. Fig. 5 is remaining energy comparison in convergence path between RA-ACA and TACA. As shown in Fig. 5, the remaining energy of RA-ACA in convergence path is about more than TACA as much as 5kWh. This shows that the proposed RA-ACA selects the larger energy as the next hop, and the transmission energy has been rationally distributed. Thus, the energy consumption speed of single node can be controlled, and the lifetime of the whole network can be also prolonged. In addition, we simultaneously consider the unidirectional links problem and node energy in the DSON, and we examine the delay performance as shown

in Fig. 6. It can be seen that only considering node energy cannot significantly improved the delay of convergence path. That is because the delay and node energy sometimes cannot be simultaneously optimum values.

V. CONCLUSION

In this paper, combined with the characteristics of deepspace laser communication, we have proposed a DSON structure based on FWMN, which supports the multi-hop transmission for DSON. In addition, we propose an efficient algorithm called RA-ACA to optimally control the transmission energy consumption of nodes for DSON, thus this scheme not only prolongs the network lifetime but also reduces the possibility of unidirectional links. Meanwhile, we make full use of the existing unidirectional links to realize the searching for optimal path in DSON. Simulation results show that this algorithm is efficient and the unidirectional links are valuable for energy conservation. Moreover, in order to enhance the convergence

speed, we reserve the node pheromone for the subsequent path finding. Compared with the TACA, the algorithm proposed in this paper can not only decrease the transmission delay but also save the node energy. In addition, the convergence speed has been significantly increased.