Node topology location method of SDN social network based on ant colony algorithm

Abstract

Due to the convergence defect of the existing SDN social network node topology location methods, there is a large node topology location error problem. In order to solve the above problems, this paper proposes a topology location method of SDN social network nodes based on ant colony algorithm. Firstly, the ant colony algorithm is introduced, and then the biological principle of ant colony algorithm is analyzed to determine the basic steps of ant colony algorithm. According to the number of mobile beacon launch positions and specific launch coordinates in ROI, ant colony algorithm is introduced into the mobile beacon path acquisition program to realize SDN node topology location based on ant colony algorithm. The experimental results show that under the background of node communication radius of 2.0 and 5.0, the node topology positioning errors of this method are small, and the minimum errors are 9.10% and 5.15% respectively. It is fully proved that this method has good node topology positioning effect.

Keywords

Ant colony algorithm SDN social network node topology positioning method

1. Introduction

The main function of SDN (system on chip) social network is to transmit and process data, which has the characteristics of low cost, strong robustness and fast deployment. These characteristics make SDN social network more and more widely used in modern society [1]. For example, in the military field, SDN social network nodes can be put into the enemy’s field to monitor the enemy’s movements; In environmental science, SDN social network nodes can monitor forest fires; in environmental science, SDN social network nodes can monitor the enemy’s movements [2]; In the aspect of agricultural cultivation, the pests on crops are detected periodically to ensure the healthy growth of crops [3]; In terms of medical and health care, doctors can timely grasp the patient’s condition through the information transmitted by the SDN social network node on the patient, so as to ensure the patient’s safety [4].

Due to the huge application value of SDN social network, SDN social network has become the focus of the community. However, most of the nodes in SDN are randomly scattered, and their location information is uncertain before that. The information sensed by unknown nodes is meaningless for SDN social network applications. Only when people first determine the location of the node, can the information transmitted by the node to the observer be complete [5]. In addition, node location information plays an important role in improving routing efficiency, naming network space, reporting network coverage quality, balancing network load and self configuring network topology. Therefore, determining the location of SDN social network nodes is the basis of SDN social network applications. If the location of SDN social network nodes can not be determined, everything will be out of the question [6]. However, the number of nodes is relatively large, and they are randomly placed, so the nodes cannot know their exact location when they are placed, so we need to take certain strategies to locate the SDN social network nodes [7]. GPS has outstanding performance in real-time, positioning accuracy and anti-interference direction, but GPS positioning needs to install corresponding facilities on each node, and the energy consumption is large. Due to the need of application, the volume of each node can not be too large, its own energy is limited and can not be recharged again. According to the existing conditions of nodes, it is impossible to configure GPS positioning device for each node. Therefore, we have to study a certain positioning algorithm and system to calculate the location of the node with less energy consumption [8]. At present, some scholars have studied this. For example, Li et al. proposed a social network node location method based on network topology heuristic clustering, and carried out network topology clustering based on modularity optimization, so as to obtain the network community division result with the highest modularity and realize social network node location [9]; Yuan et al. proposed a social network information location algorithm based on topology expansion, mining hidden information according to the state of the current network node [10]. Combined with the state of the current network node, they proposed the concepts of relationship topology and information topology, and designed a candidate source point expansion algorithm based on information topology to realize location.

Although the above scholars have studied this, the existing location methods have convergence defects, resulting in large node topology location errors. Ant colony algorithm is a probabilistic algorithm, which can be used to find the optimal path. The algorithm has the characteristics of distributed computing, positive information feedback and heuristic search, and can provide convenience for positioning. In essence, it is a heuristic global optimization algorithm in evolutionary algorithm. Therefore, this paper introduces it into this field and proposes a node topology location method of SDN social network based on ant colony algorithm, hoping to improve the existing problems through the application of ant colony algorithm

2. Node topology location method of SDN social network

2.1 Introduction of ant colony algorithm

Ant colony algorithm is a global optimization algorithm proposed by Italian scholar Dorigo in ant colony algorithm, each ant acts as a candidate solution. In the iterative optimization process, the maximum probability converges to the optimal solution of the problem. The “asymmetric double bridge experiment” can be used to analyze the path discovery process of ants in ant colony algorithm, as shown in Fig. 1.

Figure 1.

Ants from nest to food source.

As shown in Fig. 1, ants can reach the food source from the nest through A-B-D and A-C-D. The length of ABD and ACD are 2 and 4 respectively. If the speed of ants is 1, there are 20 ants in total [11]. At the beginning, the pheromone on all roads is 0.

When $t=$ 0, 20 ants start from the nest. Because the pheromone of the two paths is 0, the ants randomly choose on the two paths. Finally, 10 ants will walk on the right side and 10 ants on the left side [12].

When $t=$ 4, the ants on the a-b-d path arrive at the food source and are ready to return.

When $t=$ 5, two groups of ants meet at D, one group returns, the other group goes to the food source. At this point, the pheromone concentrations of path BD and path CD are the same, because 10 ants each chose the corresponding path before. Therefore, among the 10 ants returned, 5 will take the D-B-A path and 5 will take the D-C-A path.

When $t=$ 8, the ants that follow the D-B-A path return to the nest, while the ants that follow the D-C-A path are at C-A. the other group of ants will be divided into two groups of 5 ants, one at D-C and the other at D-B.

When $t=$ 9, the first five ants to return to the nest left the nest and reached A, and they were faced with the choice of B or C.

At this time, the pheromone concentration of A-B path is 20, and the pheromone concentration of A-C path is 15. Therefore, ants will choose A-B path with greater probability when they choose the path, and continue to enhance the pheromone concentration of the path. With the passage of time, the difference of pheromone concentration between the two paths will be larger and larger, and most ants will choose the shortest path.

The basic steps of ant colony algorithm are as follows [13]:

Step 1: $nc\leftarrow 0$ (for the number of searches or iterations); Initialization of each $\tau_{ij}$ and $\Delta\tau_{ij}$ ; $m$ ants are randomly placed on $n$ vertices.

Step 2: Put the initial starting point of each ant in the current solution set; Move each ant $k(k=1,2,\cdots,m)$ to the next vertex $j$ according to the probability formula shown in Eq. (1) and put $j$ in the current solution set of the ant until all nodes are in the solution set [14].

$\displaystyle P_{ij}^{k}(t)=\left\{\begin{array}[]{ll}\frac{\tau_{ij}^{\alpha}% (t)\cdot\eta_{ij}^{\beta}(t)}{\sum{\tau_{ij}^{\alpha}(t)\cdot\eta_{ij}^{\beta}% (t)}}&\text{if }j\in\textit{allowed}_{k}\\ 0&\text{otherwise}\\ \end{array}\right.$ (1)

Step 3: Calculate the path length $L_{k}(k=1,2,\cdots,m)$ of ant traversing all nodes; Record the best solution at present.

Step 4: Update the pheromone concentration according to Eqs (2)–(4).

$\displaystyle\tau_{ij}({t+n})=\rho\cdot\tau_{ij}(t)+\Delta\tau_{ij}$ (2) $\displaystyle\Delta\tau_{ij}=\sum\limits_{k=1}^{m}{\Delta\tau^{k}_{i}}$ (3) $\displaystyle\Delta\tau^{k}_{ij}=\left\{{{\begin{array}[]{ll}{\frac{Q}{L_{k}}}% &{\text{The kth ant passes }}ij\\ 0&{\text{other}}\\ \end{array}}}\right.$ (4)

Step 5: For all edges $({i,j})$ , set $\Delta\tau_{ij}\leftarrow 0$ , $nc\leftarrow nc+1$ .

Step 6: Judge whether the end condition is satisfied ( $n c$ reaches the maximum number of iterations or all ants find the same solution), and end the iteration if it is satisfied; Otherwise, jump to step 2.

Step 7: Output the best solution.

2.2 Calculation of the number and coordinates of mobile beacon transmitting positions

Using GPS system in SDN node topology can quickly locate nodes, but considering the scale, energy and network cost of each node in SDN social network, it is difficult to install GPS system on each node, and GPS can not work in indoor environment [15]. Therefore, using the relative distance between nodes to locate the node topology is a better choice. According to the different positioning principles, the commonly used node positioning methods can be divided into two types: range-based and range-free. The former is more accurate, but the cost of computation and communication is large; The latter is less accurate, but the cost of all aspects is small, so it is suitable for low-power, low-cost applications. This research pays more attention to the application of SDN social network in the field of precise positioning, so this research is based on the high precision range based positioning mechanism.

In the range-based positioning mechanism, the nodes in SDN social network can be divided into two categories: One is the ordinary nodes that do not have the ability to measure their own coordinates, which are the main body of the network; The other is equipped with positioning tools such as GPS, which can measure their own coordinates, which are usually called beacon nodes or beacon nodes, which are scattered in the whole network deployment area. RSSI is used to measure the distance or angle between the common node and the beacon node, and then trilateration or triangulation is used to calculate the topological position of the node. In this positioning method, the layout and number of beacon nodes have a great impact on the final positioning accuracy. Using more beacon nodes will improve the positioning accuracy, but it will increase the overhead of setting up the network. Moreover, when the positioning work is completed, the beacon node has little effect [16]. Therefore, it is a great waste to try too many beacon nodes in SDN social network. In view of this, this study introduces ant colony algorithm to obtain mobile beacon path. The specific process is as follows:

Using trilateration to locate unknown nodes requires at least three different positions which are not collinear to measure the distance between beacon nodes and ordinary nodes, and these three different positions are the radio signal transmitting positions of mobile beacon nodes. The circle with the center of all transmitting positions and the radius of the longest extended distance of RSSI must cover the whole ROI. At the same time, the number of transmitting positions should be as small as possible on the premise of fully covering ROI.

Therefore, we can transform the selection of the transmitting location and the number of locations into the problem of finding the circle with the radius of the perceived distance $R$ of the SDN social network nodes, and the problem of the minimum coverage of the ROI without vulnerability. When the centers of three equal circles A, B and C form an equilateral triangle with side length $\sqrt{3}r$ , the overlapping area without holes formed by circles A, B and C is the smallest. Therefore, if the length of the equilateral triangle formed by the radio signal transmitting position of the beacon node is $\sqrt{3}r$ , then the beacon signal transmitting position is the least and the radio signal covers the whole ROI. At this time, the coverage of each beacon transmitting point divides the ROI into a series of closely adjacent regular hexagonal grids, each grid is centered on the location of the beacon transmitting point, and the side length is $r$ , as shown in Fig. 2.

Figure 2.

Vulnerability free minimum coverage ROI grid.

As shown in Fig. 2, the described coverage is called one fold coverage, and trilateration requires distance measurement from three non collinear positions. Therefore, only one coverage is not enough, at least three coverage is needed to ensure that each ordinary node can sense the ranging signal of three beacon nodes [17]. The triple coverage of ROI is composed of three groups of one coverage, in which each emission point forms an equilateral triangle with side length $r$ , which is called equidistant triple optimal coverage. Equidistant triple optimization coverage is easily transformed into a group of coordinates in the coordinate system. The set of emission position points that constitute equidistant triple optimization coverage obtained in a rectangular ROI form a set of regular triangle meshes [18].

Through the above process, the launch position coordinates are obtained as follows:

$\displaystyle\left\{{{\begin{array}[]{l}{X_{ij}=A-({j-1})\times r}\\ {Y_{ij}=({i-1})\times\sqrt{3}/2\times r}\\ \end{array}}}\right.$ (5)

2.3 Path acquisition algorithm based on ant colony algorithm

After getting the number of mobile beacon launch locations and specific launch coordinates in ROI, considering that ant colony algorithm is a new type of simulated evolutionary algorithm, which has strong search ability, good adaptability and robustness, this study introduces ant colony algorithm into mobile beacon path acquisition [19]. TSP (traveling salesman problem) is also one of the famous problems in the field of mathematics. That is, if a traveling businessman wants to visit n cities, he must choose the path to go. The restriction of the path is that each city can only visit once, and finally return to the original city. The goal of path selection is to obtain the minimum path distance among all paths. Considering the existence of TSP problem, each launch site is regarded as a city and ant colony algorithm is introduced. The implementation steps are as follows:

Step 1: Initialization.

Let the number of initial iterations $Nc=0$ ; Set the initial value of pheromone strength to $\tau({r,s})=\tau_{0},\Delta\tau({r,s})=0$ for the path $({r,s})$ between the transmitting points of each mobile beacon. $m$ ants are randomly placed on $n$ beacon emission points, and the tabu list of ants is empty: $\textit{tabuk}=\phi$ ;

Step 2: Solving process.

$\displaystyle\text{for}({i=1;i\leqslant n;i++})$ $\displaystyle\text{for}({k=1;k\leqslant m;k++})\{$

The initial sensor node of ant $k$ is added to tabuk;

$I f$ (the ant $k$ does not complete the assigned task and the tabu list is not full),

{calculate $P_{ij}^{k}(t)$ according to Eq. (1), and ant $k$ selects the next beacon transmitting point $s$ to be visited; Move to the emission point $s$ and add $s$ to tabuk; According to Eq. (3), the path $({r,s})$ is updated locally;}

Step 3: Global update.

$\displaystyle\text{for}({k=1;k\leqslant m;k++})$

According to tabuk, find out the shortest and longest ants in this cycle;

$I f$ (there is no obvious improvement in the second iteration optimal solution, as $N$ ), the $\rho$ value is updated according to Eq. (4);

According to the formula, the optimal ant path is updated globally;

Step 4: Output the optimal solution.

$I f$ (does not meet the termination condition) {} clear the tabu list of all ants; For each path $({r,s})$ , set $\Delta\tau({r,s})=0$ ; $Nc=Nc+1$ ; Return to step 2;

Else returns to the optimal solution;

After the end of the algorithm, we get an optimized beacon node moving path. The beacon node moves to each signal transmitting point according to this path. The distance between the ordinary node and the beacon node is measured by RSSI technology. Then the trilateration positioning method is used to locate the common nodes. This research calls this new positioning method as the node topology positioning method of wireless SDN social network based on ant colony algorithm [20, 21, 22, 23].

3. Experiment and result analysis

In order to verify whether the proposed method improves the existing problems, the simulation experiment is designed on the MATLAB platform. The specific experimental analysis process is as follows:

3.1 Simulation scene settings

The standard scheme of simulation scene setting is shown in Fig. 3.

The simulation tool is MATLAB, and the simulation is carried out on PC [24, 25]. the values of parameters in the simulation are as follows: number of ants $K=8N$ ; initial step size $\lambda(0)=0.1$ ; reduction factor of step size $\xi=0.96$ ; volatility of pheromones $\rho=0.618$ ; pheromone concentration $\tau_{0}=0.1$ ; control parameter of reinitialization of pheromone concentration $\textit{renewal}=80$ ; algorithm termination parameter $\max\textit{cycle}=80$ . There is no theoretical basis for the values of the above parameters, which are mainly obtained through experience and simulation test.

3.2 Experimental results

According to the above simulation scenario setting results, the SDN social network node topology positioning simulation experiment is carried out, and the node topology positioning error is used to reflect the performance of the method. The analysis process of the experimental results is as follows:

In order to ensure the accuracy of the experimental results, experiments are carried out under the background of node communication radius of 2.0 and 5.0 respectively, and the node topology positioning error data is obtained, as shown in Table 1.

Table 1
Node topology positioning error data table

(a) Node communication radius 2.0
Number of experiments	Reference [9] methods	Reference [10] methods	Proposed method
1	32.01%	27.04%	10.23%
2	20.15%	26.13%	9.45%
3	26.45%	21.58%	10.00%
4	25.84%	26.34%	9.10%
5	21.42%	24.17%	9.40%
(b) Node communication radius 5.0
Number of experiments	Reference [9] methods	Reference [10] methods	Proposed method
1	15.02%	19.23%	5.30%
2	12.23%	18.56%	6.45%
3	12.01%	17.53%	6.02%
4	11.10%	18.21%	5.15%
5	13.56%	16.65%	5.49%

Figure 3.

Standard scheme of simulation scene setting.

As shown in Table 1, with the increase of node communication radius, the node topology positioning error shows a decreasing trend. Through numerical comparison, it is found that under the background of node communication radius of 2.0 and 5.0, the node topology positioning error of this method is less than that of the other two methods, which fully proves that the proposed method has better node topology positioning effect.

4. Conclusion

This paper mainly studies the node topology location of SDN social networks, and proposes a node topology location method of SDN social networks based on ant colony algorithm. The node location problem is transformed into an objective function optimization problem with unknown node coordinates as independent variables. The ant colony optimization algorithm is used to optimize the objective function to obtain the optimal solution of the objective function, that is, the coordinates of unknown nodes, so as to realize the node location. The experimental results show that compared with the existing methods, the node topology location method based on ant colony algorithm has smaller location error. Under the background of node communication radius of 2.0 and 5.0, the node topology location error of this method is smaller, and the minimum error is 9.10% and 5.15% respectively, which can provide a certain reference for the application and development of SDN social network. At the same time, because the design method does not conduct experimental analysis on the communication radius of more nodes, it may have an impact on the positioning results. Therefore, in the next research process, it is necessary to supplement the analysis and verification of the communication radius of more nodes, so as to make the design method have a better application prospect.

References

Zhang

Liu

. An adaptive point-of-interest recommendation method for location-based social networks based on user activity and spatial features. Knowl-Based Syst. 2019; 163(1): 267-282.

Qiao

Bai

. Segmentation of infrared images of electromechanical equipment based on the adaptive ant-colony Algorithm. Pap Asia. 2019; 2(3): 89-92.

Wang

Tong

. Multi-path unequal clustering protocol based on ant colony algorithm in wireless sensor networks. Iet Netw. 2020; 9(3): 56-63.

Wei

Tian

Peng

Liu

Zhang

. Product family flexibility design method based on hybrid adaptive ant colony algorithm. Appl Soft Comput. 2019; 23(20): 10509-10520.

Sohail

Wang

Ali

Rahim

Yao

. Efficient data handover and intelligent information assessment in software-defined vehicular social networks. Iet Intell Transp Syst. 2019; 13(12): 1814-1821.

Zhang

Han

Wang

Guizani

Fan

Shu

. A node location algorithm based on node movement prediction in underwater acoustic sensor networks. IEEE Trans Veh Technol. 2020; 69(3): 3166-3178.

Kuruba

Dushyantha

. Polygon based topology formation and information gathering in satellite based wireless sensor network. Wireless Pers Commun. 2020; 115(1): 203-237.

Grine

Gurevich

Medvedev

Zhuzhoma

. On topology of manifolds admitting a gradient-like flow with a prescribed non-wandering set. Siberian Adv Math. 2019; 29(2): 116-127.

Luo

Chai

Yuan

Gan

. Target IP city level location method based on network node clustering. Comput Res Dev. 2019; 56(3): 17-29.

10.

Yuan

Gao

Wang

. Malicious information source locating algorithm based on topological extension in online social network. Comput Sci. 2019; 46(5): 136-141.

11.

Abdolhosseinzadeh

Derakhshanfard

. CTR: Carry time-based routing for increasing delivery ratio in mobile social networks. Wireless Pers Commun. 2020; 110(3): 1271-1282.

12.

Botello-Smith

Luo

. Robust determination of protein allosteric signaling pathways. J Chem Theory Comput. 2019; 15(4): 2116-2126.

13.

Aranganathan

Suriyakala

. An efficient secure detection and prevention of malevolent nodes with lightweight surprise check scheme using trusted mobile agents in mobile ad-hoc networks. J Amb Intel Hum Comp. 2019; 10(9): 3493-3503.

14.

Houssein

Saad

Hussain

Zhu

Hassaballah

. Optimal sink node placement in large scale wireless sensor networks based on Harris’ hawk optimization algorithm. IEEE Access. 2020; 8: 19381-19397.

15.

Agrawal

Bhatia

Prakash

. Network and risk modeling for disaster survivability analysis of backbone optical communication networks. J Lightwave Technol. 2019; 37(10): 2352-2362.

16.

Aghbari

Bahutair

Kamel

. GeoSimMR: A MapReduce algorithm for detecting communities based on distance and interest in social networks. Data Sci J. 2019; 18(1): 1-20.

17.

Rana

Tripathi

Raw

. Opportunistic directional location aided routing protocol for vehicular Ad-Hoc network. Wireless Pers Commun. 2020; 110(2): 1217-1235.

18.

Banerjee

Dutta

Sufian

. Movement guided management of topology (MGMT) with balanced load in mobile ad hoc networks. Int J Inf Tech. 2019; 11(1): 149-158.

19.

Yaghoobirafi

Nazemi

. An approach to XBRL interoperability based on ant colony optimization algorithm. Knowl-Based Syst. 2019; 163(1): 342-357.

20.

Zhang

Jiang

Liu

Wang

Fan

, et al. Method of damage location determination based on a neural network using a single fiber Bragg grating sensor. Appl Opt. 2019; 58(26): 7251-7257.

21.

Cardoso

Gracia-Lazaro

Moisan

Goyal

Moreno

. Effect of network topology and node centrality on trading. Sci Rep-Uk. 2020; 10(1): 11113.

22.

Bebensee

Nazarov

Zhang

. Leveraging node neighborhoods and egograph topology for better bot detection in social graphs. Soc Netw Anal Min. 2021; 11(1): 10.

23.

Park

Demarco

. Optimal network topology for node-breaker representations with AC power flow constraints. IEEE Access. 2020; 8: 2169-3536.

24.

Dimitriou

Roussaki

. Location privacy protection in distributed IoT environments based on dynamic sensor node clustering. Sensors-Basel. 2019; 19(13): 3022.

25.

Najy

Diabat

. Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion. Transp Res Part B: Methodol. 2020; 133: 62-84.

Node topology location method of SDN social network based on ant colony algorithm

Abstract

Keywords

1. Introduction

2. Node topology location method of SDN social network

2.1 Introduction of ant colony algorithm

3. Experiment and result analysis

3.1 Simulation scene settings

3.2 Experimental results

Table 1 Node topology positioning error data table

References

Table 1
Node topology positioning error data table