Optimization of Data Analysis Algorithms for Geographic Information System

Thanks to the fast development of computer and wireless transmission technologies, information exchange and transmission have becoming increasingly convenient these days [1]. Now the one-way communication can no longer meet user needs in real-time data sharing at low costs, and the construction of networks not only consumes large amounts of material resources such as electric and optical cables, but also requires high maintenance costs [2].

Wireless ad hoc networks are a type of networks consisting of nodes connected through wireless links, since no physical circuit is needed, their configuration is flexible and the network expansion is easier, now they are a hot topic in information research [3]. Algorithm selection can affect the form and effect of ad hoc networks, so algorithm research is particularly important [4]. Conventional routing algorithms generally attain the shortest path through weighting. The traditional approaches usually require to build routes, and the process is complex, time-consuming, and costly [5]. In contrast, greedy algorithms make local decisions based on local data, there is no need to establish an entire route. On the one hand, it can reduce the maintenance cost of the network, on the other hand, the implementation effect of the algorithm can be guaranteed in case of high data volume, and the delay problem won' t show up [6].

In view of these matters, this study aims at studying and optimizing the greedy routing algorithm based on geographic location information, in the hopes of attaining higher performance and better serving the user needs.

3.png

Figure 3. The routing hole problem

The three algorithms have one thing in common: they select the nearest node for data forwarding according to their respective judgement criteria based on current node, when the current node doesn’t match with the target node, namely the next receiving node can not be found, then as shown in Figure 3, the neighbor nodes corresponding to current node S are B, C, E, and D, these neighbor nodes are not “closer” nodes for node S, then the routing hole problem would arise. Reasons for the first case of routing hole problem include obstacles, unreliable nodes, etc. Data will be lost at this time, which is not conducive to the implementation of the algorithm.

To further figure out the performance of each algorithm, based on the ad hoc network, this paper referred to the two-factor theory (node number n and node connection number m) and comparatively analyzed the performance of these three algorithms in the ad hoc network, the average packet delivery rate and hop number were selected as performance parameters. The selected experimental parameters are shown in Table 5. After averaging the results of 20 network connectivity graphs, the relationships between the average packet delivery rate and hop number are given by the curves shown in Figures 4 and 5.

Table 5. Experimental parameters

	Values	Note
Node number	20,50,100	0-100
Network connectivity graph	20	Nodes in the wireless transmission radius is sorted first nm / 2 in all side length
Source node and destination node	50

4.png

Figure 4. The data packet delivery rate

5.png

Figure 5. The path hop on average

According to above results, the greedy routing algorithm based on closest distance criterion and the greedy routing algorithm based on prior to the recent criterion outperformed the greedy routing algorithm based on direction recently criterion, in this paper, the greedy routing algorithm based on closest distance criterion was chosen as the basis of routing decisions.

3.2 Processing of the greedy routing algorithm

The routing hole problem is a challenge that can be avoided by using a greedy routing algorithm based on the information of geographical location to collect local information as much as possible so as to reduce the use of network information and the amount of data flow. At the position of each node, the greedy routing algorithm uses the local position information of neighbour nodes to create a Related Neighbour Graph (RNG), as pointed out by Giordan and Stojmenovic [10], RNG has the same connectivity as the GG (Figure 6), and the expression is:

$\forall w \neq u, v: d(u, v) \leq \max [d(u, w), d(v, w)]$

where,

u/v/w are independent vertices;

$d(u, v)$, $d(u, w)$, $d(v, w)$ are distances between nodes u and v, u and w, and w and v.

6.png

Figure 6. RNG and GG

The nodes in RNG that do not meet the conditions of the formula were filtered out by the following algorithm:

m is the midpoint of edge $\overline{u v}$

for all $v \in N$ do

for all $w \in N$ do

if w= =v then

continue

else if d(m,w)<d(u,m) then

delete edge $\overline{u v}$

break

end if

end if for

end if for

3.3 Analysis and optimization of greedy routing algorithm

3.3.1 Analysis of greedy routing algorithm

The process of data packet routing and forwarding is the complanation process of the connectivity graph. There are two methods of data forwarding: the complete traversal and the unilateral traversal methods [11]. To figure out the performance of face routing data forwarding, the paper adopted simulation experiments to study the rate of successful data delivery and the average path length extension. The selection criteria of simulation parameters are similar to those given in Table 5 of Section 3.1, and the performance parameters are:

(1) Data packet delivery rate:

$D R_A(G)=\frac{|X|}{n(n-1)}$

where,

n represents the number of nodes;

A represents the algorithm;

X represents the set of node pairs (u,v)∈G:u≠v;

|x| represents the number of elements in set X.

(2) Average path length extension:

$A D_A(G)=\frac{1}{|X|} \sum_{(u, v)} \in X \frac{A P(u, v)}{S P(u, v)}$

where,

AP(u,v) represents the number of edges in the network graph through which the effective path from node u to v passes;

SP(u,v) represents the number of edges in the network graph through which the shortest path from node u to v passes (Dijstra's algorithm).

7.png

Figure 7. Performance of greedy routing algorithm

8.png

Figure 8. Average path length of face routing and forwarding method

According to Figures 7 and 8, in terms of average path length extension, the performance of unilateral traversal is better than that of complete traversal. After the route forwarding method and the greedy algorithm were combined, the average path length extension was good, the data packet delivery rate had been improved, the merits of the two had been combined as well.

3.3.2 Optimization of greedy routing algorithm

The greedy routing algorithm protocol is a good reference for solving the routing hole problem during the forwarding process of data packets. However, when two receiving nodes have a same length value relative to the destination node and different distances relative to the source node, the data forwarding delivery of the algorithm is prone to failure [12]. In view of this problem, this paper introduced a correction parameter f to describe the quality influence of such local link, and the expression of f is:

$\left\{\begin{array}{c}f=\tan A(d-B)+C \\ d \rightarrow d_c: f \rightarrow 1 \\ d \rightarrow R_{\max }: f \rightarrow \infty\end{array}\right.$

Table 6. Simulation scenarios

9.png

Figure 9. Rate of successful data packet delivery

10.png

Figure 10. Data packet overhead

11.png

Figure 11. Data packet ratio

To verify the reasonableness and correctness of the optimization method, simulation experiment was carried out for analysis, and the experimental parameters are shown in Table 6, for other experimental parameters, please see Section 3.1. Three indicators, data packet delivery rate, path length, and algorithm overhead were selected for analysis, then the attained three parameters and node motion situations are shown in Figures 9-11.

According to the three figures above, as the retention time of node movement changes, the data packet delivery rate of the optimized greedy routing algorithm protocol is higher than that before optimization, the corresponding protocol routing has a less overhead, while for the average path length of the data algorithm, there is not a large difference before and after optimization. Overall speaking, the quality optimization of local link based on correction parameter can improve the rate of successful data packet delivery.