# A Robust Graph Theoretic Solution of Routing in Intelligent Networks

Authors: Muhammad Aasim Qureshi; Mohd Fadzil Hassan; Muhammad Khurram Ehsan; Muhammad Owais Khan; Md YeaKub Ali; Shafiullah Khan
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Implementation of robust routing is very critical in network communication. Connecting devices like routers maintain databases for the whole network topology in the routing table. Each router needs to keep these tables updated with the best possible routes so that an efficient communication can always take place in nondelay tolerant intelligent networks that include military and tactical systems, vehicular communication networks, underwater acoustic networks, and intelligent sensor networks. The fast construction of shortest-path tree (SPT) is important to devise an efficient routing in a nondelay tolerant networks. That is why a simple and efficient algorithm is the need of the time. A robust routing solution SPT withOV+E time complexity is proposed to supersede the existing landmark.


---

## Body

## 1. Introduction

Network routing is a backbone of intelligent communication networks specifically nondelay tolerant networks that include military and tactical systems, vehicular communication networks (VCNs), underwater acoustic networks (UANs), and intelligent sensor networks (ISNs) to send the communication data between vertices in a certain network. For the purpose, every router maintain routing tables. These tables manage routes of various network destinations. This network routing process is generally accomplished based on these routing tables and routes defined in them. This makes the formation, written in a memory of these routers, critically important for successful and efficient routing. There exist many graph theoretic solutions of this routing problem. In a network, the vertex of a graph represents a router, and edge/link which connect these vertices represents physical links between the routers.The needs for broadband Internet applications have increased rapidly in today’s Internet. Which makes high speed routing inevitable and has become the key at open shortest-path first (OSPF). As a result of topological changes that take place due to due to an unavoidable circumstances at the OSPF, these algorithms update the routing table to handle the new topological changes. For example, if some link fails in a network, then there is no way but to recalculate these paths [1]. In such scenarios, these shortest paths are regenerated by running the algorithms again [2].We can formally define shortest-path problem as follows:LetG=V,E, where V=v1,v2,v3,v4,⋯,vn and E=e1,e2,e3,e4,⋯,em.G is an undirected nonnegative weighted connected graph (in this scenario, it will be representing the routing network). G has a vertex “s” designated as source and another vertex, “t,”, designated as destination, such that s,t∈V. We need to find simple path(s) from s to t with minimum incurred cost.[3] presented a hybrid model with local and global modes. A fixed graph model is used to present the local mode connections. In the paper, they denoted graph by a unit-disk graph UDG(V): for any u,v∈V, {u,v} ∈ UDG(V) if and only if distance between u and v is less than 1. For the local mode, in each round, node u can send a message of Ologn bits to node v. For the global mode, they used a variant of the node-capacitated clique (NCC) model presented in [4] that describes salient features of overlay networks. In [5], the authors explain the SPSN approach including route object modeling, capacity-oriented search, and possible route organization procedures. Prototype assessments presented significant support that SPSN is better than the legacy CGR in more than an order of magnitude in contact plans comprising thousands of contacts.The shortest-path tree (SPT) problem is one of the most well-known problems in graph theory [6]. Since 1959, most of the advances in SPT for general graphs, directed and undirected, are based on Dijkstra’s algorithm. There exist lots of applications of SPT problems like computer systems, transportation networks, and vehicle routing [7]. Time complexity of the basic algorithm of Dijkstra [8] is calculated as OV2+E (where Vis number of vertices and E is number of edges) if linear search is applied to find the minimum [9]. [10, 11] introduced a new data structure, heap, to find the minimum. This new data structure improved the time complexity to OElogV. Fibonacci heap improved this bound further [12]. Authors of [12] used comparison model for the optimal implementation of Dijkstra’s algorithm as Dijkstra’s algorithm traverses vertices in ascending order.In [13], with the use of optimal structure of the data, heap data structure provides the complexity of OElogV with implementation of Dijkstra and Fibonacci heap gives the complexity of OE+VlogV with the implementation of Dijkstra. For the stochastic decision-making problem in [14], the stochastic dynamic programming solution is required. The generalized elementary shortest-path problem in [15] shows that two-phase heuristic graphs by including negative cycles can improve the average gap of 0.3% if compared with the best known solutions if number of vertices N are set to 100. The solution in [16] suggests that these algorithms can be implemented in all kind of networks with complexity of Dijkstra OV2+E, Bellman OV3, and Floyd OVE. The paper [17] suggests a solution with OkVlogkV+kE complexity for a fast delivery problem. The complexity of Bellman is OV3, and the complexity of Dijkstra is OV2 if the network is fully connected or near to the fully connected [18].Invent of fusion trees and its application in Dijkstra’s algorithm make randomized bound of time complexity,OElogV1/2. Later, the invention of atomic heaps improved this time bound to OE+nlogv/loglogVbound and OE+VlogV+ε1/2 [12]. Afterwards, in [6, 19, 20], priority queues improved to OEloglogV and OE+VlogV1+∈1/2. These worst-case time bounds are randomized supposing linear space are prerequisite. The researcher of [21] further improved it to OE+VlogVloglogV1/2 which was improved by the authors of [16], next year, using randomized bound to OE+VlogV1+∈1/3.[2] presented priority queue, which improved single source shortest-path cost to OE+VlogC1/2where C is the cost of the most heavy edge. This bound was further improved by [22] to OE+V3logCloglogC1/3 expected time, and [23] presented a further improvement to OE+VlogC1/4+∈. The authors of [24] claimed that the algorithm they have presented will outclass Dijkstra algorithm.In [25], the authors presented an exact adjacency-based primal algorithm to resolve the SPT problem with high resources. Their algorithm explored solution space iteratively using path adjacency-based partition. They claimed optimal convergence with good path in lesser cost. Authors of [26] introduced a multiobjective (time and cost) shortest-path tree problem for connected directed graphs. Every edge was having two cost values. They proved that uncertainty MSPP reduced the total travel time and cost.[27] used a dual evolutionary algorithm while analyzing the problem of clustered shortest-path tree. Their first algorithm (N-LSE) targeted the minimization of search space with fewer vertices. The second algorithm named M-LSE using N-LSE creates smaller and multiple intercluster edges. [28] solved the dynamic SP problem to solve time-dependent TSP. In logistic planning where traffic data is rich enough, time-dependent path optimization techniques give considerable benefits. Dynamic shortest-path solution contains no length k cycles and resolves the complexity problem when compared to acyclic graph-based methods.In [29], the author reviewed many popular algorithms for solving the SPT problem in weighted graphs. He proposed two variants of Dijkstra’s algorithm. He presented asymptotic comparison different variants of Dijkstra’s algorithm on expanded graphs. He presented OE′+V′lgV′ time algorithm where E′=E+Cmax−Cmax+ and V′=VCmax−+Cmax−. They used color-in and color-out scheme.


## 2. Concept

This work presents a novel algorithm of finding shortest-path routes in intelligent networks. This algorithm is based on bidirectional search where first search is starting from source vertex, and its target is destination vertex, while second search starts from the destination vertex, and its target is source vertex. It is analogous to two robots looking for each other from two distinct points. First robot,RA, starts its search from its current position, and let us call it PA, and second robot, RB, starts its search from its current position, and let us call it PB. RA explores all possible paths, in BFS fashion, looking for PB or RB. In the same way, RB will be exploring all possible paths, simultaneously, looking for either PA or RA. Following are the three possible situations that can rise, in this bidirectional search.
(i)
RA will find PB(ii)
RB will find PA(iii)
RA and RB meets at position, PMSituation i is the simplest one. LetPathA be the path that RA has explored and has vertices a1,a2,a3,⋯,ax, where ax is PB.
(1)Requiredpath=PathA=∑i=1x−1eai,ai+1.In situation ii,RB has found PA. It means that path is found but in reverse order. Let RB has explored the vertices in sequence b1,b2,b3,⋯,by, where by is PA.
(2)PathB=∑i=1y−1ebi,bi+1.The reverse of this will generate the required path. See the following equation:(3)Requiredpath=∑i=y1ebi,bi−1.In situation iii, it is little complex than the previous two. Two paths—PathA and PathB, need to be concatenated. Let PathA be the path that RA has explored and has vertices a1,a2,a3,⋯,ax. PathB is the path that RB has explored and has vertices b1,b2,b3,⋯,by, where ax and by are the same vertices as PM and a1 and b1 are PA and PB, respectively. The required path will be having vertices in the sequence a1,a2,a3,⋯,ax,by−1,by−2,by−3,⋯,b1, as given in equation (3).
(4)Requiredpath=∑i=1x−1eai,ai+1+∑i=y2ebi,bi−1.


## 3. Proposed Algorithm

The proposed algorithm targets only those graphs in which on two paths, from source,Pi and Pj, to fulfil the following property:
(5)LenPis,w>LenPjs,w,(6)∑i=0forPik−1wxi,xi+1>∑i=0forPjl−1wyi,yi+1,where k≠l and x0=y0=s and xk=yk=w and Pi and Pj are paths from s to w such that Pi=x1,x2,x3,⋯,xk and Pj=y1,y2,y3,⋯,yl.The search is executed, parallel, from both ends—source,s, and destination, t. Vertices are explored level by level. Best paths are calculated by concatenating the new edge with previously explored best path, and cost is calculated by adding the cost of all edges in that path from source.Each vertex during the execution goes through three states, being represented by three colors—green, yellow, and red. The definitions of these colors can be seen in Table1Table 1
Definitions of colors that represent the state.
ColorDefinitionGreenUnseen: the vertex is yet virgin, no neighboring vertex has yet seen/explored it and considered it to be the part of the shortest pathYellowSeen: some neighboring vertex has seen/explored it and considered it to the part of shortest pathRedVisited: this vertex has played its part and has explored all its neighbors, making them yellowInitially, all vertices, i.e.,v1,v2,v3,⋯,vn, are initialized with
(7)SPCostvi⟵∞,πvi⟵∅,Cvi⟵green.Starting from s and t, independently and simultaneously, the current vertex, let us call it vcur, will explore its neighbors. Every neighbor, i.e., vnbr, is updated with shortest-path cost, and let us call it SPCost, parent, i.e., π and color, i.e., C.
(8)SPCostvnbr=minSPCostvcur+wvcur,vnbr,SPCostvnbr,(9)πvnbr=vcurifSPCostvnbrisupdated,(10)Clrvnbr=yellowifSPCostvnbrisupdated.Update will be effective if newSPCostvnbr reflects improvement over previously stored one.Initially all vertices have green status. As soon as a vertex is explored during the search, its status is updated to yellow. As soon as any vertex completes its exploration (i.e., all its neighbors are explored, and their status is changed to yellow), its status is updated to red.Exploration takes place, strictly, level by level. No next level vertex is explored until all the previous level yellow vertices’ status is change to red. As soon as one level is completed, the control is switched to the other part of the algorithm to proceed and it also performs the identical steps.During the search of any side if some red (light or dark) vertex is explored by the counterpart search, then two shortest paths are calculated and stored. If some shortest path has already been stored, then the path will less cost will be kept.The algorithm terminates when the status of all vertices is updated to red (light or dark). In worst case, depending upon the type of the graph, it finishes inOV+E time. If graph is totally disconnected, even then loop in line number 4 of ShortestPath will execute for OV times. If graph is connected and is having E, then combined effect of line number 4 of ShortestPath and line number 2 of SPfromSource or SPfromDestination would be “all adjacents of all vertices” will cost OE which will make it OV+E. Detailed algorithm can be seen in Algorithm 1.Algorithm 1.
ShortestPath(s, t, G)1. Queue1.enQueue(s)1. Queue2.enQueue(t)2. InitializeDoubleSource(SPCost, Pi, Clr, s, t, G)3.  Flag ← 04. While (Queue1 <> Null OR Queue2 <> Null) AND Flag = 05.  Do SPfromSource(SPCost, Pi, Clr, G)6.   SPfromDestination(SPCost, Pi, Clr, G)SPfromSource(G)1. while u ← Queue1.deQueue() <> Green2. for each v belongs to Adj[u]3.  do if Clrv = Green OR LightYellow OR LightRed4.    then Clrv ← LightYellow5.      SPCostv ← min(SPCostu +W(u,v), SPCostv)6.      If SPCost is updated7.       Then Piv ← u8.      If Clrv = Green OR LightRed9.       Then Queue.enQueue(v)10.    If Clrv = DarkRed11.     Then Concatinate two paths and store12.        CPCost ← min(CPCostu + CPCostv + w(u,v), CPCost)13.    If Clrv = DarkYellow14.     then skip15. Clru ← LightRedSPfromDestination(G)1. while u ← Queue2.deQueue() <> Green2. for each v belongs to Adj[u]3. do if Clrv = Green OR DarkYellow OR DarkRed4.  then Clrv ← DarkYellow5.  SPCostv ← min(SPCostu +W(u,v), SPCostv)6.  If SPCostv is updated7.   Then Piv ← u8.  If Clrv = Green OR DarkRed9.   Then Queue.enQueue(v)10. If Clrv = LightRed11.  Then Concatinate two paths and store12.    SPCostv ← min(SPCostu + SPCostv + w(u,v), SPCostv)13. If Clrv = LightYellow14.    then skip15. Clru ← DarkRed


## 4. Working Example of the Algorithm

All vertices are initialized using equation (7) (see Figure 1). Both sources—A and P, are colored yellow and their SPCosts are marked 0 (see Figure 1(a)). All vertices are enqueued. Main subroutine (named ShortestPath) of the algorithm calls the two replicated subroutines (named SPfromSource and SPfromDestination) one by one until queue has any vertex.Figure 1
Explaining the process of the algorithm for simplification weights and other details are skipped: (a) initialization: (b) source and destination explored their neighbors; (c) neighbors of neighbors of source and destinations are explored one by one; (d) neighbors of neighbors of source and destinations are explored one by one.
(a)(b)(c)(d)The subroutine SPfromSource dequeues a vertex, it would be source, and here in this example, it isA. Algorithm then explores all its neighbors—B, F, and E, one by one.Equations (8)–(10) are used to update the values of SPCost, π, and Clr. In the same way, SPfromDestination dequeues a vertex, it would be destination, and here in this example, it is P. Algorithm then explores all its neighbors—L and K, one by one. Equations (8)–(10) are used to update the values of SPCost, π, and Clr. A and P are colored red after all explorations. New updated status can be seen in Figure 1(b).In the same way, SPfromDestination dequeues a vertex, and it would be path, equations (9) and (10). Figures 1(c), 1(d), and 2(a) explain these iterations one by one. Figure 2(b) shows that a red vertex is explored from the other side. It generates case 3 (i.e., “RA and RB meet at position, PM”). Path from both sides along with currently updating edge is concatenated to form a path using equation (7). This path is stored.Figure 2
(a) Extract one vertex from queue from both sides and explore their neighbors; (b) explore a red vertex; applying case 3, path is calculated and stored; (c) repeat until all vertices change their color to red, and if new path is shorter, then it is stored and old one is skipped. Finally, the shortest path is obtained.This process of dequeuing, exploring, and generating new path continues until both queues have no vertices. New paths are generated and compared with the stored one and is discarded if old one is better Figure2(c). But if new path is better than the old one, it is replaced with the old one. The process ends with the shortest possible path.


## 5. Discussion

The main advantage of this algorithm is due to the nature of the networks in which it is not possible that indirect distance can be smaller than direct distance between two vertices. Since Dijkstra invented his SPT algorithm, the research community has worked mostly in the similar direction: choose a node to propagate in nondecreasing order and manage and update neighboring vertices through it. To select vertices in a nondescending order, the half-explored vertices must be sorted, or on each selection, the minimum distance must be calculated from the remaining vertices, which again is equivalent to sort [29].The main bottleneck of these algorithms is the intermediary sorting algorithm. Most researchers have worked to surmount this bottleneck. New data structures like tree, heap, and priority queue were designed to improve the time bounds. One of these is Fibonacci heap [30] that resulted in the best known asymptotic bound of Dijkstra’s algorithm [31]. However, this bound is also criticized by researchers due to the heavy processes of Fibonacci heap [32–37]. This algorithm is beating this bound of Dijkstra’s algorithm using Fibonacci heap, where sorting is not being attempted in any form. On one side, it is thrashing this time bound with simple data structure and no sorting algorithm; on the other side, it has parallelization in its nature that is beyond the scope of this paper.At the same time, this algorithm is also better than the one presented in [29] with worst-case time bound of OE′+V′lgV′ time algorithm where E′=E+Cmax−Cmax+ and V′=VCmax−+Cmax−. The algorithm proposed in this research has worst-case time bound ofOV+E, which is linear in time and hence is better than the one presented in [29] for routing in intelligent networks [38–42].


## 6. Conclusion

The proposed SPT algorithm executes withOV+E time which is relatively better than the state of art work. It is simple to understand and easy to implement and does not require high computational resources. It has additional benefit that after some specific stage, it can always hold a path from source to destination if compromise on quality of path is possible to address the latency issues in nondelay tolerant networks that include military and tactical systems, vehicular communication networks, underwater acoustic networks, and intelligent sensor networks.



---

*Source: 9661411-2022-06-20.xml*