More

How to create a Processing script using the shortest path algorithm?


I'm currently using the Road Graph plugin to find the shortest path in a road network - however, I'd like to put this to a processing script (to be used in a model later) and the Road Graph Plugin has no API to be used in a model.

Is there a way to put the shortest path algorithm to a processing script and then use this script in a model?

I found some python scripts for networks/shortest path in the Python Cookbook and tried to put it to a processing script - but as I am a complete newbie with python I didn't get far…

The script should:

  • Take a roadnetwork (blue) and and a line vector layer (violet) as input
  • Put the start (green) - and endpoint (red) of the line as start and end of the path to be claculated
  • Use the intersections of the input line and the network as waypoints, that the path should follow
  • Find the shortest path (red ribbon) by routing through the network and save the path as vector layer

Can anybody help me with this script?


You can find multiple versions of routing scripts which use the QGIS network analysis library in my Github repository, e.g. https://github.com/anitagraser/QGIS-Processing-tools/blob/master/2.2/scripts/point_layer_to_route.py which converts an ordered set of points into a route.

None of the scripts use the intersections of an input line with the network. That's something you will have to add on your own.


Multiple object tracking using the shortest path faster association algorithm.

Multiple object tracking is a hot topic in the field of computer vision. Robust tracking of objects is important for many computer vision applications, such as human-computer interaction, video surveillance, intelligent navigation [1, 2]. Apart from a high performance detection algorithm as an auxiliary, high quality multiobject tracking should also track the algorithm for support, which can address certain types of complex cases, for example, illumination, occlusion, clutter, and so on [3]. The data association (DA) method is a favorite for multiobject tracking. The often utilized techniques include the nearest neighbor method [4], joint probability data association [5], and methods based on neural networks [6].

The effect of the DA methods mentioned above is closely related to the detection accuracy in adjacent frames. These typical approaches are resilient to false negatives and false positives: if an object is not detected in a frame but is in previous and following frames, it is a false negative. A false positive is mistaking the tracking object "A" as object "B." Although this problem can be solved using targeted design a statistical trajectory model with filtering [7, 8], the calculation method that provides the maximum posterior probability is NP-complete.

Recent papers have proposed different approaches to this problem. Giebel et al. [9] use sampling and particle filtering to remove clutter from the same object and reduce the probability of NP-completeness. This method obtains a relatively accurate tracking trajectory but requires a sufficient number of sampling points. Perera et al. [10] divides a long sequence into several short ones, yielding lots of short tracking tracks, and links them using Kalman filtering. This can avoid the NP-completeness. The accuracy of this method is inversely proportional to the length of the short tracking tracks, the shorter the length, the better the tracking. However, the excessive division increases the computation time, due to which the method cannot track objects for long time. Fleuret et al. [11] processes trajectories individually over long sequences using reasonable greedy dynamic programming (DP) to choose the order. These approaches, while effective, cannot attain the global optimal solution.

Zhang's approach [12] relies on a min-cost network flow framework-based optimization method to find the global optimum for multiple object tracking. However, the two algorithms he proposes have several defects in practice and their complexity is polynomial. Under this framework, Berclaz et al. [13] formulate multiobject tracking as an integer programming (IP) problem and reduce it to linear programming (LP). By relying on the k-shortest paths (KSP) algorithm for the optimization of the LP problem, their approach reduces the complexity to perform robust multi-object tracking in real time. However, because of KSP's lack of a motion model over dynamic programming (DP), the tendency of the DP to ignore fragmentary trajectories makes it more robust. Pirsiavash [14] continues the work of Zhang and uses his method to obtain the global optimal solution with the greedy algorithm for K = 1 in O(N) but only obtains the approximate solutions for K > 1 in O(KN), where K is the unknown optimal number of unique tracks.

By contrast, in this paper, we effectively combine the models proposed by Zhang and Berclaz to devise a more efficient framework for the shortest path faster algorithm (SPFA). Not only can the SPFA algorithm directly obtain the global solution, it also shows the advantage of the DP motion model, which enables the algorithm to ignore incomplete trajectories and behave more robustly against this type of noise. Moreover, it is far better with respect to both the worst-case complexity and the run time than the above-mentioned state-of-the-art algorithms. Our main contributions in this paper are as follows.

(1) Based on the min-cost network model, we introduce a novel general mathematical integer programming formulation for multiobject tracking. The proposed IP method is conducive to naturally filtering out false positives and false negatives using SPFA.

(2) To solve the integer linear programming formulation of the proposed framework and to obtain the global optimal solution, we propose to use the more rapid and more efficient SPFA algorithm. Compared with the state-of-the-art methods of [13, 14], the SPFA algorithm can improve the running time obviously while the multiobject tracking precision and accuracy are not loss.

The rest of this paper is organized as follows. In Section 2, we formulate an IP using the min-cost network flow framework and relax it to continuous LP. Section 3 contains our proposed shortest path faster algorithm for the relaxation of the original IP. We introduce approaches to target localization and long sequence segmentation processing in Section 4. Section 5 contains the experimental results and a complete evaluation metrics. Finally, conclusions are drawn in Section 6.

The target motion of multiobjet tracking can be better described using the relationship between the neighborhood locations that use the DP method in a min-cost network flow framework. We define an objective function for multiobject tracking in the same manner as in 13]. The objective presence of likelihood will be estimated by the marginal posterior probability in every frame, thereby obtaining the potential trajectory of the moving object.

2.1. Min-Cost Flow Model. We formulate the multiobject tracking as a process, where the objective location of each object discretely changes in continuous time. A directed 3D spatiotemporal group with random variable [k.sub.t] is used to describe the video sequence. Consider

[k.sub.t] = (x, y, t), [k.sub.t] [member of] V, (1)

where [k.sub.t] denotes any location of an object in this spatiotemporal group at time t, V is the set of all space-time locations in a sequence, and x and y are the pixel positions of the target in the transverse and longitudinal axes, respectively.

For any location kt at time t, the neighborhood N([k.sub.t]) [subset] <1,2, . K>denotes the locations that an object can reach at time t + 1. A single track as an ordered set of state vectors T = ([k.sub.1], . [k.sub.N]), and X = ([T.sub.1], . [T.sub.L]) is a set of tracks. We assume that the tracking tracks are independent of each other and describe the network flow framework of multiobject tracking using the dynamic model as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

[P.sub.source] ([k.sub.1]) is the probability of a tracking track starting at location [k.sub.1] and [P.sub.sink] ([k.sub.N]) is the probability of a tracking track ending at location [k.sub.N].

In the spatial coordinate set V, a binary indicator variable [[phi].sub.i,t] represents the directed flow from location [k.sub.i] to location [k.sub.t] that is, it stands for the number of objects moving from [k.sub.i] to [k.sub.t]. [[phi].sub.i,t] is 1 when the space-time locations [k.sub.i] and [k.sub.t] are included in some track, given that the object is at [k.sub.t-1] at time t, which means that an object remains at the same spatial location between times t - 1 and t. For locations [k.sub.t] and [k.sub.j] at time t + 1, some constraint conditions are executed for the variable [[phi].sub.i,t]:

[for all][k.sub.t], [summation over ([k.sub.1], [k.sub.t] [member of] N ([k.sub.i]))] [[phi].sub.i,t] (3)

[for all][k.sub.i],[k.sub.t], [summation over ([k.sub.t] [member of] N ([k.sub.i]))] [[phi].sub.i,t] [less than or equal to] 1. (4)

Let a random variable [M.sub.t] stand for the true presence of an object at location [k.sub.t] in space time. For every instant of time t, the detector is used to check every location of the tracking zone. The marginal posterior probability of an existing object is calculated as follows:

where [I.sub.t] is the single image at frame t. We write m = <[m.sub.t]>for a feasible set of the likelihood probability distributions for the existence objects in V by the method in Section 4.1. M is the spatial set of [M.sub.t]. The likelihood probability of the existence of an object in the given set of tracks X is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

[M.sub.t] is conditional independence in X. We can infer the maximum posteriori estimate of tracks by the probability distributions of the existence of objects:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

where (10) is true because [m.sub.t] is 0 or 1 according to (4), and (11) is obtained by ignoring a term that does not depend on [m.sub.t]. The cost value of a directed flow between the neighborhood locations of any adjacent frames is defined as

c([e.sub.t,t+i]) = - log ([(rho).sub.t]/1 - [(rho).sub.t]), (13)

where [e.sub.t,t+1] is a directed edge from location [k.sub.t] at time t to location [k.sub.t+1] at time t+1, and the total cost between any two locations in V is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

2.2. Integer Linear Programming. In our framework, because the objects can enter and leave the tracking area, we introduce additional nodes for the source and sink that have been defined proposed by [13]. Equations (7)-(12) can then be translated naturally into an integer linear program (ILP):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

where the constraint conditions are the same as (3) and (4), and [[phi].sup.*] = argmin C([phi]) is the optimal solution of the ILP. C([e.sub.source,i]) is the total cost of the flow from the source node to the locations of the tracking track, and C([e.sub.i,sink]) is that from the locations of the track to the sink node. Figure 1 shows a simple flow network constructed from multiobject tracking, where the costs are c([e.sub.i,j]) for blue edges, c([e.sub.source,i]) and c([e.sub.j,sink]) for black edges.

The costs are defined as follows:

c([e.sub.source,i]) = - log [P.sub.source] ([k.sub.i]), c([e.sub.i,sink]) = - log [P.sub.sink] ([k.sub.i]). (16)

The relaxation of the IP using standard methods is NP-complete. In general, the variants of the simple algorithm [15, 16] or the interior point based methods [17, 18] can be used to solve this problem. However, these algorithms have very high worst-case time complexities. In [13, 14], whereas the methods of KSP and successive shortest path (SSP) can relax the IP successfully to continuous LP, both of them have their own deficiencies. We use the SPFA algorithm to compensate the deficiencies of these methods.

3. Fast Dynamic Shortest Path Algorithm

In this paper, we use the shortest path faster algorithm to relax the integer program by the network flow framework the average case complexity of this algorithm is O(E). The global optimum of the SPFA algorithm makes the tracking more reliable and more efficient. The network flow framework needs two particular properties to realize the SPFA algorithm as follows.

(1) All edges and nodes are independent of each other all edges are unit capacity.

(2) The network is a directed acyclic graph (DAG).

3.1. SPFA Algorithm. The shortest path faster algorithm has been proposed in [19]. The data structure of the SPFA algorithm uses an adjacency list and a First-in, First-out (FIFO) queue. Applying the dynamic optimal approach, the time complexity of SPFA algorithm is O(E), where E is the number of edges in the graph. It is better than the complexity of Dijkstra's algorithm, E [much less than] [N.sup.2], where N is the number of nodes. No particular limitation conditions are needed for this algorithm. Therefore, the SPFA algorithm can be adopted for all directed graphs, except for the ones where negative weight cycles are reachable from the source.

3.2. SPFA Algorithm with Virtual Nodes. Let C be the total cost of any location in space V, and let E be the set of the edges between adjacent frames of any neighborhood location. The state transition between any pair of nodes of the model can be attained by E, and the DAG G(V, E, C) can completely describe the flow activity of an object of the min-cost flow model.

In our min-cost flow model, Q is a FIFO queue, L denotes an adjacency list used to store G(V,E,C), and c([e.sub.i,j]) is an element of L. Let array D record the current cost of a directed flow from source to all other nodes. The total cost value of the shortest path from the source to v is stored in array D(v). In the initialization, each element of array D has its maximum value. Array D will then output the shortest path between the source and the sink through the SPFA algorithm when queue Q is empty.

To improve the robustness of multiobject tracking in an environment of false negatives, we define [G.sub.r] as the residual graph of G(V, E, C) that denotes all locations from the current node to the terminal node. Two additional virtual nodes, source and sink, are introduced into [G.sub.r] and are linked to all nodes representing locations. We can then find the shortest path between node source and node sink by the SPFA algorithm in [G.sub.r]. Moreover, the shortest path between source and node v can be obtained in array D, where v is any node in the shortest path from the source to the sink.

In the proposed min-cost flow framework, we can obtain the shortest path through the following steps.

(1) Create the FIFO queue Q, the adjacency list L, and the array D. Initialize D(j) := [infinity] and D(source) := 0, where source is the beginning node and j is any other node. Add source to the queue Q.

(2) Add all neighborhood nodes that can be reached form source to Q and record their cost values in array D. Let D(i) store the total cost value of the shortest path from the source to the node i, i [member of] [G.sub.r].

(3) Assess the neighborhood nodes j of the new node i in Q, where j is the node that can be reached from node i. If D(i) + c([e.sub.i,j]) < D(j), D(j) := D(i) + c([e.sub.i,j]).

(4) Iterate (3) until queue Q is empty and the shortest path T = ([k.sub.1], . [k.sub.N]), [k.sub.N] [member of] [G.sub.r], between source and the node v can be obtained in array D, where v is any node in the shortest path from source to sink.

Figure 2 shows the simple processing steps of the SPFA algorithm in our proposed model. Here, birth represents the node where an object was first discovered, and end is that where it was last discovered. Each relaxation operation using the SPFA algorithm is a process of the current node visiting adjacent nodes. The nth relaxation operation ensures that the path is the shortest in n. As the length of the edge for the shortest path in the residual graph does not exceed N - 1, the path that we obtain using the SPFA algorithm is the shortest one. Compared with the method in [14], which uses the SSP algorithm with the additional greedy method, the SPFA algorithm can find the global optimum. Its convergence has been proved in Theorem 2 of [19].

It is not sufficient to be able to track multiple objects by the SPFA algorithm because some target movements during this process are easily overlooked. To enable the SPFA algorithm to better describe the movement of the target, we offer additional constrains for the algorithm.

3.3. Constraints for SPFA Algorithm. When we search the shortest path between birth and end in the original residual graph Gr, one problem arise. It is that the algorithm cannot handle the entry and departure of the object in any position between birth and end that is, the tracking process is incomplete and not robust.

To improve the tracking robustness by the SPFA algorithm, we use the neighbors of birth and end to replace the original position and form a new DAG with the virtual positions source and sink, as shown in Figure 1. Source and sink here denote the positions where an object appears and disappears, respectively. This method can optimize the dynamic correlation between the nodes of the SPFA algorithm.

Moreover, at no iteration the SPFA algorithm generates a large amount of calculation because there are only three neighborhood locations calculated in each relaxation for a node, and the number of available nodes is inversely proportional to the number of iterations.

3.4. Time Complexity Analysis. The Dijkstra's algorithm is recognized as an effective method to compute the shortest path in 0(N log N) time. Unfortunately, in our proposed flow network, there are negative costs, which contradict the precondition of the Dijkstra's algorithm. Fortunately, there are no negative weight cycles in the proposed model and thus the SPFA algorithm can be adopted.

The proposed algorithm is an optimization of the Bellman-Ford algorithm. While we blindly go through each edge for N rounds in the Bellman-ford algorithm, a queue is maintained in SPFA to make sure that we only check the relaxed nodes. SPFA is simpler than the O(NE) of the Bellman-Ford algorithm, where N is the number of nodes and E is the number of edges.

For the DAG, the average case complexity of the SPFA algorithm is O(E), where E is the number of edges in the graph. In this case, each node enters the queue only once. The SPFA algorithm is a breadth-first search algorithm, which is the common case in our proposed approach. If each node enters the queue N-1 times, the proposed algorithm degenerates into the Bellman-Ford algorithm with a time complexity that is the worst-case complexity of that algorithm, that is, O(NE). The complexity of the SPFA algorithm in the general case has been proved in [19]. Reference [20] analyzes the theoretical and experimental worst-case complexity of the SPFA algorithm in detail.

References [13,14] propose the KSP and SSP algorithms, respectively, to compute the relaxation of the integer linear program. The worst-case complexity of both algorithms is 0(KN log N), where K is the unknown optimal number of unique tracks and N is the frame number of the video sequence. Note that because of the different values of K, 14] uses different methods to obtain the solution. The specific complexity of this algorithm is related to the value of K.

The average case complexity of our proposed algorithm is O(E), which is far less than that of the above mentioned methods. The worst-case complexity of the SPFA algorithm is O(NE), but this almost is never obtained.

Moreover, like the KSP algorithm, the SPFA algorithm successfully calculates the global optimal solution, as proved in [19]. However, SSP with the greedy algorithm as in [14] cannot obtain the global optimal solution.

4. Target Localization and Long Sequence Processing

High quality multiobject tracking requires a reliable tracker, a detector that can accurately segment and locate multiple objects, and a preprocessing method that can improve the performance of the algorithm.

4.1. Target Detection and Localization. To obtain the accurate target for the tracker, we establish a background model with the improved codebook algorithm and extract the observed characteristic information of the tracking object by the foreground/background subtraction method of [21]. Using the method from [22], we segment objects that were initially merged together. We then obtain the probability distributions of the planes of the objects from the detector, and these can serve as the input to the SPFA algorithm. A few selected frames of target localization are shown in Figure 3.

Full range tracking in the camera field of view increases the processing time of the algorithm and consumes a significant portion of the limited memory resources. For this reason, because most of the calculated probabilities of the objective presence are 0, we can reduce the number of nodes and computational cost by this characteristic. On the other hand we limit the potential birth area of targets to reduce the amount of computation. The proposed method also checks the maximum detection probability of each location [k.sub.t] within a given spatiotemporal neighborhood of each frame t:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

If the value at a location is below the set threshold, an object represented by the value is considered unable to reach the location, and all flows from and to it are removed from the model. This method can reduce by an order of magnitude the number of required variables and constraints. In our experiment, we pruned the graph by a radius of [[epsilon].sub.1] = [[epsilon].sub.2] = 3.

4.2. Long Sequence Processing. In theory, processing a long sequence using the SPFA algorithm can yield the global optimum for tracking time but requires a large amount of operation time. To address this issue, we split the long sequence into segments of 100 frames each, which yields good results with a delay of less than 0.5 seconds between input and output and can be performed in real time.

For each segment maintaining temporal consistency, we use the method of multiframe overlay, as shown in Figure 4, and add the last 10 frames of the previously optimized segmentation to the first 10 frames of the current one.

We then force the sum of flows of every location of the first 10 frames of the current frame to be consistent with the total number of flows of the last locations of the object in the last 10 frames of the previous one. This effectively solves the problem of the missing target on the piecewise point:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

where [[theta].sub.t] is the total flow of the last position [k.sub.t] of object appearing in the last 10 frames of the previous segment. For the corresponding first position [k.sub.j] of an object appearing in the first 10 frames of the current segment, the net flow into it is equal to the flow out of position [k.sub.t] and is also equal to the total flow out of any potential position [k.sub.i] of any object between [k.sub.t] and [k.sub.j]. This is implemented as an additional constraint in our model.

If we cannot find the tracking target in the first 10 frames of the current segment, the proposed method searches for the object in t' frames after the current one. In our experiment, we let t' = 10. If we find the tracking target in a frame within t', this frame is the first frame of the current segment the tracking fails otherwise.

In our simulation, video sequences with different characteristics were selected from the PETS09, CAVIAR, BEHAVEDATA, and ETHMS (BEHAVEDATA, http://groups.inf.ed.ac.uk/vision/BEHAVEDATA/INTERACTIONS/index.html, CAVIAR, http://groups.inf.ed.ac.uk/vision/CAVIAR/CAVIARDATA1/, ETHMS, http://www.vision.ee.ethz.ch/

aess/dataset/, and PETS09, http://www.cvg.rdg.ac.uk/data-sets/index.html) datasets. The challenges for each of these are summarized in Table 1. The selected sequences cover almost all problems that commonly occur in multiobject tracking.

5.1. Parameter Setting. In the training period, a detector is designed using the background subtraction method of the improved codebook algorithm model. We combine the detection result with the activity scope of the object by foreground/background segment update in real time and calculate the location of the object with a high probability. Because the size of the activity scope of the object and the number of the pixels of the object are not identical in every sequence, our method can generate 900-1000 detections per frame in each video sequence. We set the log-likelihood ratio of each detection process to be the negative score as the results of the linear detector.

We used a bounded value dynamic model: we define the cost [c.sub.i,j] between two locations in consecutive frames in the case of spatial overlap (i.e., an object remains at a location) as 0. The costs from the virtual location to the neighborhood of birth and end are [C.sub.source,birth] = 10, [C.sub.end,sink] = 10, respectively. Moreover, because global search using SPFA is in the established adjacency list, finding the shortest path must be the global optimal solution without auxiliary constraints.

5.2. Evaluation Metrics. Let [GT.sub.i,t] be the ith ground truth bounding box for the fth frame, and let [TR.sub.i,t] be the tracked bounding box. [C.sub.i,t] for the fth frame and ith object is defined as the ratio between the area of intersection [GT.sub.i,t] [intersection] [TR.sub.i,t] and the area of union [GT.sub.i,t] [union] [TR.sub.i,t] [23]:

In our experiment, we set the threshold of [C.sub.i,t] to 0.5, which means that the tracking is successful when the overlapping areas of the ground truth bounding box and tracked bounding box exceed 0.5.

Our results are evaluated using the multiple object tracking accuracy (MOTA) and multiple object tracking precision (MOTP) metrics of the standard CLEAR2006 metrics [24]:

MOTA = 1 [[SIGMA].sub.t] ([c.sub.m] ([m.sub.t]) + [c.sub.f] ([fp.sub.t]) + [c.sub.s])/[SIGMA].sub.t] [g.sub.t], (20)

MOTP = [[SIGMA].sub.i,t] [C.sub.i,t]/[[SIGMA].sub.t] [Nm.sub.t], (21)

where [g.sub.t] is the number of ground truth objects in the tth frame, [Nm.sub.t] refers to the number of mapped objects in the tth frame, [m.sub.t] represents the missed detection count, and [fp.sub.t] is the false positive count for each frame. [c.sub.s] = [log.sub.10]ID- [SWITCHES.sub.t], where ID-[SWITCHES.sub.t] is the number of ID mismatches in t considering the mapping in frame t - 1. We started the count from 1 because of the log function. [c.sub.m] and [c.sub.f] represent, respectively, the cost functions for missed detections and false positives. The values used for the weighting functions in (20) are [c.sub.m] = [c.sub.f] = 1. Figure 5 shows the histograms of MOTA and MOTP in the experiment using the SPFA algorithm.

5.3. Analysis of Results. To ensure the unique identification for each tracking target, we use different colors to indicate the order. The sequences used in our experiment are from Table 1. The detection results are obtained by the process described in Section 4.1 as the input of our algorithm. We then conduct a performance test of the multiobject tracking circumstances of false positives, false negatives, and a dynamic background, respectively.

5.3.1. Performance Test for False Negatives. The sequences use Multiple_flow_view1 and S2_L1_view5 from the PETS09 dataset. We show typical results in Figures 6 and 7. In particular, the former uses bright yellow coats worn by pedestrians as the tracking object. Although the probability of false negatives increases significantly because of occlusion with nontracking objects, the SPFA algorithm can ensure persistent tracking (the color of the tracking box has not changed) for each object in the entire tracking process. The experiment for S2_L1_view5 verifies the robustness of the SPFA algorithm when the targets leave the area of nonrestricted departure and reappear soon.

5.3.2. Performance Test for False Positives. The sequences use the Threepastshop2 of the CAVIAR dataset and Sequence3 of the BEHAVEDATA dataset. Typical results are shown in Figures 8 and 9. We used the method from Section 4.1 for detection and localization. Because of the superior solution and anti-interference of the SPFA, we can stably track multiple objects in a timely fashion in case of false positives.

5.3.3. Performance Test for Dynamic Background. There are two conditions that must be satisfied by the sequence of the experiment.

(1) The available probability distribution of the dynamic background of the sequence needs to be relatively consistent. Only in this way can the algorithm quickly obtain the location of an object for tracking.

(2) The targets should be fixed access areas in the tracking ground. Because the tracking ground is moving, the potential area in which the objects can enter and exit changes. We require the borders of the camera field of view to be the area for all objects that can enter and exit.

The sequence uses Seq03view1 from the ETHMS dataset. We obtain object characteristics by the method of combining skin color and the method in [25] and show the typical results in Figure 10. The method of detection and localization in Section 4.1 only considers the available probability distribution of the target characteristic in the tracking ground and does not relate to the background conditions. Therefore, the sequence for our experiment requires a consistent probability distribution. This constraint, in a way, limits the experimental conditions of performance for a dynamic background but does not affect the conclusion that multiobject tracking using the SPFA algorithm in a dynamic background is robust.

5.4. Simulation Analysis. All of above experiments were performed on a Windows XP PC equipped with a 2.7 GHz Pentium (R) Dual-Core CPU and 8 GB of memory. The software platform uses Visual Studio 2010 and Open CV2.2.

We contrasted the SPFA algorithm with three other algorithms (Zhang's method 2 [12], KSP [13], and SSP [14]) in two sequences from different datasets (Seq03view1 of the ETHMS dataset and Sequence3 of the BEHAVEDATA dataset) with regard to the average tracking errors. The results are shown in Figure 11. We also compared the algorithms with respect to the tracking accuracy. Figure 12 shows detection rate versus false positives per image (FPPI) for all algorithms. We use the same detection method detailed in Section 4.1 for all our experiments.

Figure 11 shows that the tracking errors of these algorithms are not significantly different in cases not involving occupancy and clutter. However, when tracking an object in the case of false positives and false negatives for a long time, our SPFA algorithm exhibits clear superiority. Although the occupancy problem in the case of simple assumptions can be satisfied by Zhang's method 2, the required assumptions result in omission and eventually lead to tracking failure when several false negatives and false positives occur frequently. In Figure 12, when the above algorithms have the same target detection rate, the SPFA algorithm performs better than other algorithms in controlling FPPI. The superiority of the SPFA algorithm is due to its faster relaxation method and to finding the global optimal solution more quickly.

With the same target detection method as above, we compared the false positives generated using SPFA method with those from the other methods on the ETHMS dataset and the CAVIAR dataset, as shown in Table 2. The results show that the SPFA algorithm can track better. Further, as shown in Figure 13, the run time of the SPFA algorithm significantly outperforms the other three algorithms.

5.5. Run Time. We evaluated the speed of our SPFA tracking algorithm on the sequences of the BEHAVEDATA dataset at 25 fps. The curves of the run time for SPFA and the above algorithms have been shown in Figure 13. The vertical axis representing run time is plotted on a log scale. The solution of Zhang's method 2 does not converge for a significant running time. When dealing with a sequence of 1000 frames, the KSP solver takes approximately 20 seconds and SSP takes 0.9 seconds, but our SPFA solver only takes 0.08 seconds.

In this paper, we proposed a reliable tracker with a flow network framework. In the min-cost flow model established by the theory of integer program, we then used SPFA algorithm to relax the integer assumption and to successfully identify the global optimal solution. The resulting algorithm can better solve the problems of short-time false positives and false negatives in multiobject tracking and is more robust than state-of-the-art methods. Our proposed method can quickly find the global optimal solution of the relaxed LP by using SPFA.

Experiment results indicate that the proposed algorithm is helpful in improving trajectory consistency and solving serious occlusion problems between multiple objects and can satisfy real time measurement requirements. Compared with other algorithms, there are obvious advantages of SPFA. Tracking multiple types of targets with a dynamic background in real time will be the focus of our future research.

The authors declare that there is no conflict of interests regarding the publication of this paper.

This work is jointly supported by the National Natural Science Foundation of China (Grants nos. 61372090 and 61210013) and the National Key Project for Basic Research of China (2013CB329403).

[1] I. S. Kim, H. S. Choi, K. M. Yi, J. Y. Choi, and S. G. Kong, "Intelligent visual surveillance--a survey," International Journal of Control, Automation and Systems, vol. 8, no. 5, pp. 926-939, 2010.

[2] Z. Hou and C. Han, "Survey of visual tracking," Acta Automatica Sinica, vol. 32, no. 4, pp. 603-617, 2006 (Chinese).

[3] M.-X. Jiang, H.-Y. Wang, and X.-K. Liu, "A multi-target tracking algorithm based on multiple cameras," Acta Automatica Sinica, vol. 38, no. 4, pp. 531-539, 2012 (Chinese).

[4] H. Zhou, "A survey of multiple targets tracking technique," ACTA Aeronautica et Astronautica Sinica, vol. 7, no. 1, pp. 1-10, 1986 (Chinese).

[5] Q. Yu and G. Medioni, "Multiple-target tracking by spatiotemporal Monte Carlo markov chain data association," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 12, pp. 2196-2210, 2009.

[6] F. Serratosa, R. Alquezar, and N. Amezquita, "A probabilistic integrated object recognition and tracking framework," Expert Systems with Applications, vol. 39, no. 8, pp. 7302-7318, 2012.

[7] E. Maggio, M. Taj, and A. Cavallaro, "Efficient multi-target visual tracking using random finite sets," IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 8, pp. 1016-1027, 2008.

[8] I. Sharp, K. Yu, and T. Sathyan, "Positional accuracy measurement and error modeling for mobile tracking," IEEE Transactions on Mobile Computing, vol. 11, no. 6, pp. 1021-1032, 2012.

[9] J. Giebel, D. Gavrila, and C. Schnorr, "A bayesian framework for multi-cue 3D object tracking," in Proceedings of the European Conference on Computer Vision, pp. 241-252, 2004.

[10] A. G. A. Perera, C. Srinivas, A. Hoogs, G. Brooksby, and W. Hu, "Multi-object tracking through simultaneous long occlusions and split-merge conditions," in Proceedings of the 24th IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '06), pp. 666-673, June 2006.

[11] F. Fleuret, J. Berclaz, R. Lengagne, and P. Fua, "Multicamera people tracking with a probabilistic occupancy map," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 2, pp. 267-282, 2008.

[12] L. Zhang, Y. Li, and R. Nevatia, "Global data association for multi-object tracking using network flows," in Proceedings of the 26th IEEE Conference on Computer Vision and Pattern Recognition (CVPR '08), pp. 342-349, June 2008.

[13] J. Berclaz, F. Fleuret, E. Turetken, and P. Fua, "Multiple object tracking using k-shortest paths optimization," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 9, pp. 1806-1819, 2011.

[14] H. Pirsiavash, D. Ramanan, and C. C. Fowlkes, "Globally-optimal greedy algorithms for tracking a variable number of objects," in Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 11), pp. 1201-1208, Providence, RI, USA, June 2011.

[15] B. Aghezzaf and T. Ouaderhman, "An interactive interior point algorithm for multiobjective linear programming problems," Operations Research Letters, vol. 29, no. 4, pp. 163-170, 2001.

[16] M. D. Gonzalez-Lima, A. R. L. Oliveira, and D. E. Oliveira, "A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming," Computational Optimization and Applications, vol. 56, no. 3, pp. 573-597, 2013.

[17] J. Wei and M. Zhang, "Simplex model based evolutionary algorithm for dynamic multi-objective optimization," in AI 2011: Advances in Artificial Intelligence, vol. 7106 of Lecture Notes in Computer Science, pp. 372-381, Springer, Heidelberg, Germany, 2011.

[18] I. U. Khan, T. Ahmad, and N. Maan, "A simplified novel technique for solving fully fuzzy linear programming problems," Journal of Optimization Theory and Applications, vol. 159, no. 2, pp. 536-546, 2013.

[19] D. Fanding, "A faster algorithm for shortest-path--SPFA," Journal of South West Jiaotong University, vol. 29, no. 2, pp. 207212, 1994 (Chinese).

[20] X. Zhengdong, B. Tianming, and Z. Juyang, "Analysis and improvement of SPFA algorithm," Computer Science, vol. 41, no. 6, pp. 180-184, 2013 (Chinese).

[21] M. H. Sigari and M. Fathy, "Real-time background modeling/subtraction using two-layer codebook model," in Proceedings of the International MultiConference of Engineers and Computer Scientists (IMECS '08), vol. 1, Hong Kong, China, March 2008.

[22] A. Bugeau and P. Perez, "Track and cut: simultaneous tracking and segmentation of multiple objects with graph cuts," EURASIP Journal on Image and Video Processing, vol. 2008, Article ID 317278, 2008.

[23] H. P. Liu, M. Y. Yuan, F. C. Sun, and J. W. Zhang, "Spatial neighborhood-constrained linear coding for visual object tracking," IEEE Transactions on Industrial Informatics, vol. 10, no. 1, pp. 469-480, 2014.

[24] R. Kasturi, D. Goldgof, P. Soundararajan et al., "Framework for performance evaluation of face, text, and vehicle detection and tracking in video: data, metrics, and protocol," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 2, pp. 319-335, 2009.

[25] C.-N. Guan, C.-F. Juang, and G.-C. Chen, "Face localization using fuzzy classifier with wavelet-localized focus color features and shape features," Digital Signal Processing, vol. 22, no. 6, pp. 961-970, 2012.

Zhenghao Xi, (1,2) Heping Liu, (1) Huaping Liu, (2) and Bin Yang (3)

(1) School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China

(2) State Key Laboratory of Intelligent Technology and Systems, Tsinghua University, Beijing 100084, China

(3) Department of Electronic Engineering, Changwon National University, Changwon 641-773, Republic of Korea

Correspondence should be addressed to Zhenghao Xi [email protected]

Received 19 March 2014 Revised 22 July 2014 Accepted 30 July 2014 Published 17 August 2014


3 Answers 3

Instead of storing a single value for each candidate path in Dijkstra's algorithm, store a tuple of (total length, total profit). Consider a path shorter in the relaxation step if the total length is less, or the total lengths are the same but the total profit is higher.

Basically what you are doing is you have two arrays maintaining length and profit respectively. You can create another array which will ratio of length to profit of edges. So the array will store ratio = length/profit for all edges and the using this ration array, you can use Djikshtra's algorithm. For Djikshtra's algorithm, use V set as vertex and array ratio. Using this run Djikshtra's algorithm. You will get your required answer

One way to approach such a problem is to make a new variable, L for lambda.

But first, let's deal with the profit issue: Your edges have lengths l and profits p . Redefine all of the p such that p'=max(p)-p . Now, your maximally profitable edge has a value of zero (lowest possible) and your least-profitable edge has a value of max(p) (highest possible). You can now find the least cost-path.

Define the weight of an edge as being l*L+p'*(1-L) , now vary L from 0 to 1. Different paths will be optimal depending on whether the length or profit is more important. Loosely speaking, these paths form a Pareto optimal set. Each solution path is better than all others for that particular value of L . For that L there is no way to increase profit without also increasing length, or to decrease length without decreasing profit.

Note that choosing appropriate values of L to generate this set may not be straight-forward: for instance, if profit numbers are much larger than length numbers, most of the set will cluster in values of L which scale the profit values to a level where they are comparable with the length values. These L values may be quite small.

Ooop, saw your edit: "First find the value x of the shortest path, then over the set of all the paths with the same length x, find one with the maximum profit." In this case, Nick's answer is the way to go.


Preemptive SJF

In Preemptive SJF Scheduling, jobs are put into the ready queue as they come. A process with shortest burst time begins execution. If a process with even a shorter burst time arrives, the current process is removed or preempted from execution, and the shorter job is allocated CPU cycle.

Consider the following five process:

Process Queue Burst time Arrival time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Step 0) At time=0, P4 arrives and starts execution.

Process Queue Burst time Arrival time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Step 1) At time= 1, Process P3 arrives. But, P4 has a shorter burst time. It will continue execution.

Step 2) At time = 2, process P1 arrives with burst time = 6. The burst time is more than that of P4. Hence, P4 will continue execution.

Step 3) At time = 3, process P4 will finish its execution. The burst time of P3 and P1 is compared. Process P1 is executed because its burst time is lower.

Step 4) At time = 4, process P5 will arrive. The burst time of P3, P5, and P1 is compared. Process P5 is executed because its burst time is lowest. Process P1 is preempted.

Process Queue Burst time Arrival time
P1 5 out of 6 is remaining 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Step 5) At time = 5, process P2 will arrive. The burst time of P1, P2, P3, and P5 is compared. Process P2 is executed because its burst time is least. Process P5 is preempted.

Process Queue Burst time Arrival time
P1 5 out of 6 is remaining 2
P2 2 5
P3 8 1
P4 3 0
P5 3 out of 4 is remaining 4

Step 6) At time =6, P2 is executing.

Step 7) At time =7, P2 finishes its execution. The burst time of P1, P3, and P5 is compared. Process P5 is executed because its burst time is lesser.

Process Queue Burst time Arrival time
P1 5 out of 6 is remaining 2
P2 2 5
P3 8 1
P4 3 0
P5 3 out of 4 is remaining 4

Step 8) At time =10, P5 will finish its execution. The burst time of P1 and P3 is compared. Process P1 is executed because its burst time is less.

Step 9) At time =15, P1 finishes its execution. P3 is the only process left. It will start execution.

Step 10) At time =23, P3 finishes its execution.

Step 11) Let's calculate the average waiting time for above example.


Networkx, using shortest paths to make shortest cycles

this question is specific to NetworkX. I could make my own functions to accomplish all the things I need, but it would take much longer so I want to avoid it.

I have an unweighted graph, represented by a NetworkX Undirected Graph. From this graph, I seek "shortest cycles" - that is to say, for a given node k, I am finding the shortest simple path (only passes through a node once), that leaves k and then comes back to k.

To accomplish this, I would like to use any NetworkX Shortest Paths algorithm, and do the search from node k, to node k. The problem is, it seems that every shortest path algorithm simply returns node k as the path. So, it never actually leaves. And, I don't know how to change this.

A possible solution would be for me to do:

However, the sheer number of times I plan on doing this "shortest cycle" technique is extremely huge, and I would prefer to not have to do that. So, is there an easier way to do what I want with NetworkX?


How to create a Processing script using the shortest path algorithm? - Geographic Information Systems

Use Git or checkout with SVN using the web URL.

Work fast with our official CLI. Learn more.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.


Modelling dynamic routing for 3D shortest path analysis

Universiti Teknologi Malaysia, 81310 UTM Skudai, Johor, Malaysia.

2Department Photogrammetry and Geoinformatics,

Stuttgart University of Applied Science, Schellingstr. 24 70023 Stuttgart, Germany.

problem is its ability to handle “multiple heterogeneous modifications”: between updates, the input graph is allowed to be restructured by an arbitrary mixture of edge insertions, edge deletions, and edge-length changes.The chapter is organized in three general parts. The first part discusses the 3D navigation model, dynamic weight and its functional requirements. The second part presents the 3D dynamic network model and elaborates on the possible solution using SSSP routing algorithm and its implementation. Final discussion on recommendations for future research concludes the chapter.

Keywords: Shortest path, dynamic weight, 3D navigation, 3D-GIS.

necessary at each junction etc. A slope road with no junction still can be modeled with two nodes and one arc for routing purposes even if it is long and has a lot of serpentines as usual in the mountains but this is the geometry part of the network.

Before continuing, let us describe some notations and define the basic shortest path problem. A network is a graph, G = (V, E) consisting of set of nodes (vertex) V, with the collection of network nodes g = |V| g = |V1, V2, V3. Vn| and a spanning set of directed edges E with h = |E| h = |(V1, V2), (V2, V3), . (Vn, Vn)|. Each edge is represented as a pair of nodes, from node i to node j, denoted as (i, j). Each edge (i, j) has a weight, associated with a numerical value, Wij, which represents the distance or cost of the edge (i.e. Wij : 5). In this chapter, we assume that two-directional travel between a pair of nodes i and j is represented by two different directed edges (i, j) and (j, i). Given a network G = (V, E) with known edge weight (distance) Wij for each edge (i, j) subset to E, the shortest path problem is to find the shortest distance path from a source node s to a specific node in the node set V. This is a simple way of finding shortest path in a network, with a static node(s). There are some cases where behavior (i.e. location, weight & related surrounding attributes) of one or more nodes are dynamically change due to unforeseen events in the future, either along or surround the route to the destination.

Currently, research efforts have been initiated by researchers to introduce concepts for routing in 3D-GIS (Ivin et al., 2006 and Zhu et al., 2006) and even for evacuation strategies (Shi and Zlatanova 2005) with several types of developments and approaches. Most of the discussed researches were based on transportation data model (Zhu et al., 2006 Liu et al., 2005 Fischer, 2004) and others are focusing on disaster and emergency management (Shi and Zlatanova, 2005 Zlatanova et al., 2005 Zlatanova and Holweg, 2004). What is missing is the mapping of the real world or a 3D model to the weights or costs of an edge in a network graph.

2.0 3D NAVIGATION DATA MODEL

(NavTech), GIS-T Enterprise (Dueker and Butler, 1997), and lane-based data model (Fohl et al., 1996).

To improve current data models and construct new data models/standards, studying the concept and logic model is the base. GDF, which became an ISO standard in early 2004, is more a common concept and logic model of road networks and road related information for navigation service. And its physical model can act as exchangeable format for navigation data. However, SDAL are more physical data models. The concept and logic data model study based on GDF is meaningful.

Graph data structure allows an edge to connect to other edges only at its end points. Fohl et al. (1996) suggested a way to adapt the lane-based network to work with the existing routing algorithms by representing a lane segment with a series of small edges so that lane changing can be made to adjacent lanes at any vertex along the series.

2.1 Concept of Dynamic Weight

In vehicle routing problem, destination node is fixed, whereas the start node would be dynamically located anywhere on the map. For example, call for a taxi a person calls a taxi company and gives his/her location to the operator. Then the operator will searched and dispatched the nearest taxi to the given location and informed the caller the estimated time of arrival of the taxi. With a dynamic factor such as road traffic taking into account, the assigned taxi might not be able to arrive at the specific location in time. Other available taxi (second nearest) will then be notified, and the process goes on until a taxi reached the caller. Algorithm that will be used for this type of problem will have one-to-many type Therefore this type of case is much easier than the following problem.

While in rescue operation planning, the model of a building can either be an abstraction of a building is represented with polygons in 3D space (Zlatanova et. al 2004) which is likely geometry or topology model, or a logical model, which represents the connections between the rooms. The rooms and important crossings are represented with nodes the paths are represented as links between nodes. Therefore scenario such as “would the model be able to assign each rescuer to survivor(s) in a rescue operation and evacuation process with known or unknown number of survivor in case of a fire situation?” can be solved.

Detailed discussion about the efficiency analysis of shortest path algorithms can be found in Zhan and Noon’s (1998) research.

Navigating indoors and outdoors virtually need to have 'seamless' continuation between them. By using simulation (Jafari et. al 2003), it may improve the dynamic understanding of navigation. Some information will be temporarily unavailable in some special situation such as poor weather or technical problem, therefore the use of simulation information will provide continuous and dynamic support. Simulation of environment scenarios under different assumptions may minimize the costs and threats with a predicted manner.

3.0 3D DYNAMIC NETWORK MODEL

In short, the overall process of building a 3D dynamic network can be shown briefly in three steps. Firstly, from planar and non-planar networks to 3D networks, the ambiguous situation of under/overpass and network overlay in the 2D graph can be clarified. It improves the abilities of visualization and effective and comprehensive data integration. Secondly, by moving from a static network to a dynamic network, real-time information about the vehicle and other events can be directly integrated into the routing process. Lastly, after optimization, the unnecessary vertices are eliminated and the total number of vertices is greatly reduced, thus improve the ability of rapid response.

3.1 Anticipated Routing Algorithm Implementation

As mentioned before the routing graph might change over time due to specific events. As we will see, the two most important changes are increasing and decreasing the costs of an edge and inserting a new edge into the graph. Other events can be modelled based on these two operations. Inserting a new edge e=(v,w) to a graph can be considered as decreasing the costs c(e) from ’ to a value c. Deleting an edge e=(v,w) is similar to increase the costs of an edge to ’. Deleting a vertex v can be done by deleting all edges that are incident to v. Inserting a vertex is trivial as long as no edge is connecting it with the rest of the graph. These connecting edges will be inserted using the inserting edge algorithm. Table 1 below described when it is required to delete, insert or modifying an edge or vertex.

Table 1: Description of dynamic events for routing algorithm.

Task Example (Dynamic Events)

An edge might be blocked due to a disaster (ceiling collapse in buildings or road accidents) and can not be used any more.

In case of fire, more time is taken when rescuer uses ladder to rescue people from first floor, etc.

Modifying costs of an edge

More difficult to take this way out (due to smoke, etc.) or more easy to take this way out due to rescue team appearance.

In order to find the shortest way out of a building in case of an emergency from a given location or in traffic jams, the Single-Sink Shortest Path problem (SSSP) has to be solved for the dynamic graph G. Under the assumption that every edge e=(v,w) in the graph has positive costs c(e)>0, the problem can be solved by Dijkstra algorithm. If the structure of the graph changes due to some event, the whole algorithm has to be run again even if the changes do not have any effect on the result. The Dijkstra algorithm can be considered as batch processing on a given input graph G and sink Vertex s. If the data input is changed, the algorithm as to be run again. In this chapter we propose an incremental approach to deal with the changes of the graph structure. Changes in the graph structure are usually local changes. Once the SSSP problem is solved for the given input (G, v), only a small part of the solution has be recalculated due to the event. This incremental approach is usually much more efficient. For a detailed analysis of complexity of this kind of incremental algorithms can be found in Ramalingam and Reps’s (1996) research.

3.2 Incremental SSSP Algorithm

The input of the SSSP problem is a graph G (V, E), a cost function c: E Æ R+ and a sink vertex v. The shortest distance dist (w) from v for every vertex w V should be computed. Dijkstra algorithm will solve the problem. However, G changes over time as discussed before. We are interest in an incremental algorithm that handles these changes without solving the SSSP problem for the whole graph again.

a vertex could be reached on two different paths with the same costs. In this case, the resulting shortest paths do not build a spanning tree any more but a directed acyclic graph (DAG).

Vertex 0 1 2 3 4 5 6 7 8


Shortest Path Based Geographic Routing In Clustered Wireless Sensor Network

networks (WSNs) is to dynamically organize the sensors into a wireless network and route the sensory data from sensors to a sink. Clustering in WSNs is an effective technique for prolonging the network lifetime. In most of the traditional routing in clustered WSNs assumes that there is no obstacle in a field of interest. Although it is not a realistic assumption, it eliminates the effects of obstacles in routing the sensory data. Here, we first propose a clustering technique in WSNs named energy-efficient homogeneous clustering that periodically selects the cluster heads according to a hybrid of their residual energy and a secondary parameter, such as the utility of the sensor to its neighbors. In this way, the selected cluster heads have equal number of neighbors and residual energy. We then present a route optimization technique in clustered WSNs among obstacles using Dual algorithm. By using this technique we can discovery route even when an obstacle occurs. The route will be the best shortest path. Our work reduces the average hop count, packet delay, and energy-consumption of WSNs and extends the lifetime of sensor.

Key Words: wireless sensor network (WSN), cluster, route optimization

A wireless sensor network (WSN) consists of spatially distributed autonomous sensors to monitor physical or environmental conditions, such as temperature, sound, pressure, etc. and to cooperatively pass their data through the network to a main location. The more modern networks are bi-directional, also enabling control of sensor activity. The development of wireless sensor networks was motivated by military applications such as battlefield surveillance today such networks are used in many industrial and consumer applications, such as industrial process monitoring and control, machine health monitoring, and so on.

The WSN is built of "nodes" – from a few to several hundreds or even thousands, where each node is connected to one (or sometimes several) sensors. Each such sensor network node has typically several parts: a radio transceiver with an internal antenna or connection to an external antenna, a microcontroller, an electronic circuit for interfacing with the sensors and an energy source, usually a battery or an embedded form of energy harvesting. Sensor nodes can be partitioned into a number of small groups, which is known as clusters. These are the organizational unit for wireless sensor networks. Each cluster has the coordinator, called cluster head (CH). In a clustering scheme the sensor nodes in a WSN are divided into different virtual groups, and they are allocated geographically adjacent into the same cluster according to some set of rules. The cluster heads can consolidate the data and send it to the data center as a single packet, thus reducing the overhead. Clustering has advantages for reducing useful energy consumption by improving bandwidth utilization, reducing wasteful energy consumption by reducing overhead. Most of the algorithm aims to extend the network lifetime by balancing energy consumption among nodes and by distributing the load among different nodes from time to time.

In this paper, we propose the following:

 We propose an EHC technique in WSNs that periodically selects CHs according to their residual energy and the utility of the sensor to its neighbors. The main difference between existing clustering techniques and EHC technique is the utility of the CHs in WSNs. In the EHC technique, a sensor becomes a CH if the utility of the sensor is higher than its neighbors.

 By using EHC technique, we can extend the lifetime of sensor.

© 2016, IRJET | Impact Factor value: 4.45 | ISO 9001:2008 Certified Journal

| Page 1530

 We present a route optimization technique in clustered WSNs among obstacles using DUAL(Diffusing Update Algorithm) algorithm.

A) Group connectivity model for industrial wireless sensor networks

It is a recent trend to consider wireless sensor networks in harsh industrial environments. With actual deployment of wireless sensor networks, it would be desirable to make a concrete deployment plan regarding connectivity’s and to place sensors by grouping them according to the planned deployment points, even more in case of targeting multiple objects to be sensed and monitored in harsh environments. The connectedness of groups as well as individual sensors is important specifically for real-time data acquisitions and even more if there are no external communication links among these groups. In this paper, we focus on the connectivity of sensor groups, rather than the individual sensors only, and propose a novel group connectivity model so as to analyze group connectivity and to make a concrete deployment plan of sensor groups with regard to the internal distribution of sensors and group positions. We believe that the proposed model should be useful in planning the deployment of wireless sensor networks in harsh industrial environments where running wires is less practical and also prohibitively expensive.

B) Fuzzy-logic-based clustering approach for wireless sensor networks using energy predication

In order to overcome the problem of the limited power of the sensor battery and thus prolonging the lifetime of a Wireless Sensor Network (WSN), many routing algorithms were proposed to gather and forward the sensed data to the base station. One of the most well-known routing algorithms that were proposed in the last years is the LEACH protocol. It is a dynamic cluster-based routing protocol that divides the network lifetime to rounds where each round is composed of two phases: setup and steady state. The key factor of each round is the number of nodes that will act as cluster heads (CHs). Each CH is responsible for collecting the sensed data from the sensor nodes that are in the same cluster and then forwarding the aggregated data to the base station. In this paper we suggest FL-LEACH protocol that employs fuzzy logic in order to determine the number of CHs that should be used in the WSN. FL-LEACH is a fuzzy inference system that depends on two variables: number of nodes in the network and nodes density. Assuming uniform

distribution of the nodes over the sensor field, the novelty of the proposed approach is in its ability to determine the number of CHs without getting other information about the network. Matlab simulation is used to show the effectiveness of the FL-LEACH protocol compared with other protocols, such as the pure LEACH and the genetic-based protocol, LEACH-GA. Simulation results have shown that FL-LEACH outperforms LEACH and LEACH-GA in terms of network lifetime.

C) A general self-organized tree-based energy-balance routing protocol for wireless sensor network

Wireless sensor network (WSN) is a system composed of a large number of low-cost micro-sensors. This network is used to collect and send various kinds of messages to a base station (BS). WSN consists of low-cost nodes with limited battery power, and the battery replacement is not easy for WSN with thousands of physically embedded nodes, which means energy efficient routing protocol should be employed to offer a long-life work time. To achieve the aim, we need not only to minimize total energy consumption but also to balance WSN load. Researchers have proposed many protocols such as LEACH, HEED, PEGASIS, TBC and PEDAP. In this paper, we propose a General Self-Organized Tree-Based Energy-Balance routing protocol (GSTEB) which builds a routing tree using a process where, for each round, BS assigns a root node and broadcasts this selection to all sensor nodes. Subsequently, each node selects its parent by considering only itself and its neighbors' information, thus making GSTEB a dynamic protocol. Simulation results show that GSTEB has a better performance than other protocols in balancing energy consumption, thus prolonging the lifetime of WSN.

 Improved More Efficient Packet Delivery Ratio  Detecting And Preventing Attacks

 No Improved Security Features  Increase Routing Overhead

III IMPLEMENTATION OF TECHNIQUES

Network Configuration

© 2016, IRJET | Impact Factor value: 4.45 | ISO 9001:2008 Certified Journal

| Page 1531

communicates only within the communication range. So, we have to find the node’s communication range. A network consists of N sensors, deployed at random uniformly in a FoI among obstacles. The sensors are stationary and powered by the batteries. We assume the binary disc communication model in which a sensor, denoted by s, can communicate with other sensors within the disc of radius C centered at s. Two sensors i and j can communicate with each other directly and are known as neighbors if the Euclidean distance between them is not more than C. The number of neighboring CHs of a CH is said to be the CH degree.

Energy-Efficient Homogeneous Clustering

In this module, we first propose EHC technique and then describe its properties. EHC works in the following two steps to form a clustered WSN:

Initial cluster head election: The goal of this step is to elect the CHs in a distributed manner. At the beginning of each round, sensor i picks a random number in (0, 1). If the random number is less than P, then sensor i is a CH-candidate. With this mechanism, approximately k of N sensors are elected as CH-candidates. The random number does not depend on the previous round. Advertisement contention occurs when multiple CH-candidates advertise at the same time. To resolve the contention, we use a randomized back-off delay.

Connected network formation:We elect more CHs to ensure that the CHs can form a connected network, since ICHs are not connected. A Non-Cluster Head sensor (NCH) is elected as a CH, denoted by Gateway CH (GCH), if two or more neighboring ICHs are not connected.

A CH represents either a GCH or ICH. Preference is given to the NCHs which have higher amount of residual energy and maximum number of neighboring CHs.

We estimate the randomized back-off delay to resolve the advertisement contention for selecting GCHs.

The sensor which has the highest value of the residual energy becomes the CH. The residual energy is calculated using the formula given below

RE = Einit – ( PTx * NT)

REResidual Energy EinitInitial Energy

NT Number of transmission

During the reformation of clusters, the cluster head is changed along with the members affiliated to it. Clustering provides resource utilization and minimizes energy consumption in WSNs by reducing the number of sensor nodes that take part in long distance transmission. In WSN the primary concern is the energy efficiency in order to extend the utility of the network.

Route Optimization Technique

The goal of a route optimization technique is to achieve a path from the source to the sink but we also want to achieve the goal at a minimum cost, i.e. shortest path in terms of hop counts among obstacles. Most of the literature on routing in WSNs does not have any special treatment for the obstacles in a FoI. In this module, we propose DUAL (Diffusing Update Algorithm) in clustered WSNs that optimizes the path length during data transmission without any extra overhead.

Cluster Heads Selection

Same as, the threshold of cluster heads is set in Equation as follows:

where P is a ratio of cluster heads among all sensors, 1/P is the expected number of nodes in one cluster, rise the index of the current round and G is the set of nodes that have not been cluster heads in the last rmod(1/P) rounds.

In our proposed algorithm, we consider the network to be heterogeneous, where there are m percentages advanced nodes which have the additional energy factor (α) in itself compared with normal nodes. In to deal with this kind of heterogeneous sensor network, SEP has been proposed, and discussed in detail. With these advanced and normal nodes, this kind of heterogeneous layout has no effect on the density of the network. Hence, the previous set of Popt has no need to change. We assume the initial energy to be E0. The energy of advanced node in our proposed sensor network is E0 •(1+ α). The total energy of new Heterogeneous network is calculated:

N

(1−m)E0+N

M

E0(1+α)=N

E0

(1+αm)

Hence, the total energy increases by (1+ α•m) times. Virtually there are n•(1+ α•m) nodes with energy equal to the initial energy of a normal node. Based on equations of probabilities for advanced and normal nodes, which discussed in detail in, we improved the selection method with the residual energy of certain sensor nodes. As is shown in Equation, the weighed probability for normal nodes is:

Residua

© 2016, IRJET | Impact Factor value: 4.45 | ISO 9001:2008 Certified Journal

| Page 1532

ALGORITHM IMPLEMENTATION

Cluster formation

We elect more CHs to ensure that the CHs can form a connected network, since ICHs are not connected. A Non-Cluster Head sensor (NCH) is elected as a CH, denoted by Gateway CH (GCH), if two or more neighboring ICHs are not connected. The randomized back-off delay for a NCH i is denoted by,

Thus, a NCH with the higher residual energy and a number of neighboring ICHs will be elected as a GCH with high probability among neighboring GCH-candidates. If a NCH i wants to associate with a CH j, where j has a minimum CH degree in ni , i sends an associate message (denoted by Casso( j, i, ni )) to j and receives a subsequent confirmation message (denoted by Ccon f (i, j, n j )) from j . A NCH updates information of neighbor i whenever it receives Ccon f ( j, i, ni )) message from i.

An isolated sensor will become a CH. Therefore, each sensor in WSN is either a CH or a member of a cluster. All CHs are connected is the second property of connected WSNs. if a sensor has two or more neighboring ICHs, which are not connected, the sensor will become a GCH. in a connected clustered WSN is that each NCH has exact one CH. That each NCH allows to associates with only one CH.

Procedure: Cluster Formation

Output: GCH 1 if i is a CH then

2 if receive Casso(i, j, n j) message from a NCH j then

3 Send Ccon f( j, i, ni) message to j

4 if receive Cadve( j, E j, n j) message from a GCH j then

5 Add j in neighbor list ni 6 Send Ccon f( j, i, ni) message to j

IV. SYSTEM IMPLEMETNATION

Network simulator 2 is used as the simulation tool in this project. NS was chosen as the simulator partly because of the range of features it provides and partly because it has an open source code that can be modified and extended.

Network simulator (NS) is an object–oriented,

discrete event simulator for networking research. NS provides substantial support for simulation of TCP, routing and multicast protocols over wired and wireless networks. The simulator is a result of an ongoing effort of research and developed. Even though there is a considerable confidence in NS, it is not a polished product yet and bugs are being discovered and corrected continuously.

NS is written in C++, with an OTcl1 interpreter as a command and configuration interface. The C++ part, which is fast to run but slower to change, is used for detailed protocol implementation. The OTcl part, on the other hand, which runs much slower but can be changed very fast quickly, is used for simulation configuration. One of the advantages of this split-language program approach is that it allows for fast generation of large scenarios. To simply use the simulator, it is sufficient to know OTcl. On the other hand, one disadvantage is that modifying and extending the simulator requires programming and debugging in both languages.

© 2016, IRJET | Impact Factor value: 4.45 | ISO 9001:2008 Certified Journal

| Page 1533

proposes gradient routing with two-hop information for industrial wireless sensor networks to enhance real-time performance with energy efficiency. Two-hop information routing is adopted from the two-hop velocity-based routing, and the proposed routing algorithm is based on the number of hops to the sink instead of distance. Additionally, an acknowledgment control scheme reduces energy consumption and computational complexity. The simulation results show a reduction in end-to-end delay and enhanced energy efficiency.

The hop count refers to the number of intermediate devices through which data must pass between source and destination. Each time packets are passed to the next device, a hop occurs. Hop count is therefore a basic measurement of distance in a network.

© 2016, IRJET | Impact Factor value: 4.45 | ISO 9001:2008 Certified Journal

| Page 1534

without route optimization technique requires more number of the average hop count for routing the packets.

C. PACKET DELIVERY RATIO

The packet delivery ratio of a flow is the ratio of the number of packets that are received by the sink over packets submitted to the network by the source.

Delay is the measurement of the time for the packet to reach its destination beyond the described time. Two sensors i and j can communicate with each other directly and are known as neighbors if the Euclidean distance between them is not more than C. The number of neighboring CHs of a CH is said to be the CH degree.

In EHC, only CHs remain active to provide the routing and therefore prolongs the lifetime of WSNs. Power consumption should be minimized since it determine the lifetime of network.

© 2016, IRJET | Impact Factor value: 4.45 | ISO 9001:2008 Certified Journal

| Page 1535

of routing path, hence the lifetime of WSNs is increased. The results demonstrated that the geometry and location of the obstacles should be considered to compute an optimized routing path.

In future, to reduce the energy consumption for route discovery, we can propose a new route discovery method. In this method, the source node calculates a circle around the location of destination node which gives the list of destination's neighbor nodes. The source node defines its forwarding zone (a cone) to be the region enclosed by an angle whose vertex is at source node's location and whose sides are tangent to the circle calculated for destination. Source node sends a RREQ packet for destination to all its neighbors in the forwarding zone. Each of these neighbors forward the RREQ packets accordingly. When destination receives the RREQ packets, it will send the RREP packets back to the source node. If source node does not receive an RREP within a time period due to any obstacle in the forwarding zone, then source node resorts to a recovery procedure.

1. J. H. Lee, T. Kwon, and J. Song, “Group connectivity model for industrial wireless sensor networks,” IEEE Trans. Ind. Electron., vol. 57, no. 5, pp. 1835– 1844, May 2010.

2. J.-S. Lee and W.-L. Cheng, “Fuzzy-logic-based clustering approach for wireless sensor networks using energy predication,” IEEE Sensors J., vol. 12, no. 9, pp. 2891–2897, Sep. 2012.

3. Z. Ha, J. Wu, J. Zhang, L. Liu, and K. Tian, “A general self-organized tree-based energy-balance routing protocol for wireless sensor network,” IEEE Trans. Nucl. Sci., vol. 61, no. 2, pp. 732–740, Apr. 2014. 4. D. C. Hoang, P. Yadav, R. Kumar, and S. Panda,

“Real-time implementation of a harmony search algorithm-based clustering protocol for energy-efficient wireless sensor networks,” IEEE Trans. Ind. Informat., vol. 10, no. 1, pp. 774–783, Feb. 2014.

5. M. Tarhani, Y. S. Kavian, and S. Siavoshi, “SEECH: Scalable energy efficient clustering hierarchy protocol in wireless sensor networks,” IEEE Sensors J., vol. 14, no. 11, pp. 3944–3954, Nov. 2014.

6. P. T. A. Quang and D.-S. Kim, “Enhancing real-time delivery of gradient routing for industrial wireless sensor networks,” IEEE Trans. Ind. Informat., vol. 8, no. 1, pp. 61–68, Feb. 2012.

7. J. Niu, L. Cheng, Y. Gu, L. Shu, and S. K. Das, “R3E: Reliable reactive routing enhancement for

wireless sensor networks,” IEEE Trans. Ind. Informat., vol. 10, no. 1, pp. 784–794, Feb. 2014.


Dijkstra's Algorithm

Dijkstra's algorithm, published in 1959, is named after its discoverer Edsger Dijkstra, who was a Dutch computer scientist. This algorithm aims to find the shortest-path in a directed or undirected graph with non-negative edge weights.

Before, we look into the details of this algorithm, let’s have a quick overview about the following:

  • Graph: A graph is a non-linear data structure defined as G=(V,E) where V is a finite set of vertices and E is a finite set of edges, such that each edge is a line or arc connecting any two vertices.
  • Weighted graph: It is a special type of graph in which every edge is assigned a numerical value, called weight
  • Connected graph: A path exists between each pair of vertices in this type of graph
  • Spanning tree for a graph G is a subgraph G’ including all the vertices of G connected with minimum number of edges. Thus, for a graph G with n vertices, spanning tree G’ will have n vertices and maximum n-1 edges.

Problem Statement

Given a weighted graph G, the objective is to find the shortest path from a given source vertex to all other vertices of G. The graph has the following characteristics-

  • Set of vertices V
  • Set of weighted edges E such that (q,r) denotes an edge between vertices q and r and cost(q,r) denotes its weight

Dijkstra's Algorithm:

  • This is a single-source shortest path algorithm and aims to find solution to the given problem statement
  • This algorithm works for both directed and undirected graphs
  • It works only for connected graphs
  • The graph should not contain negative edge weights
  • The algorithm predominantly follows Greedy approach for finding locally optimal solution. But, it also uses Dynamic Programming approach for building globally optimal solution, since the previous solutions are stored and further added to get final distances from the source vertex
  • The main logic of this algorithm is basedon the following formula-
    dist[r]=min(dist[r], dist[q]+cost[q][r])

This formula states that distance vertex r, which is adjacent to vertex q, will be updated if and only if the value of dist[q]+cost[q][r] is less than dist[r] . Here-

  • dist is a 1-D array which, at every step, keeps track of the shortest distance from source vertex to all other vertices, and
  • cost is a 2-D array, representing the cost adjacency matrix for the graph
  • This formula uses both Greedy and Dynamic approaches. The Greedy approach is used for finding the minimum distance value, whereas the Dynamic approach is used for combining the previous solutions (dist[q] is already calculated and is used to calculate dist[r])

Algorithm-

  • Cost Adjacency Matrix for Graph G, say cost
  • Source vertex, say s
  • Spanning tree having shortest path from s to all other vertices in G

Following are the steps used for finding the solution-

Step 1 Set dist[s]=0, S=ϕ // s is the source vertex and S is a 1-D array having all the visited vertices

Step 2: For all nodes v except s, set dist[v]= ∞

Step 3: find q not in S such that dist[q] is minimum // vertex q should not be visited

Step 4: add q to S // add vertex q to S since it has now been visited

Step 5: update dist[r] for all r adjacent to q such that r is not in S //vertex r should not be visited dist[r]=min(dist[r], dist[q]+cost[q][r]) //Greedy and Dynamic approach

Step 6: Repeat Steps 3 to 5 until all the nodes are in S // repeat till all the vertices have been visited

Step 7: Print array dist having shortest path from the source vertex u to all other vertices

Let’s try and understand the working of this algorithm using the following example-

Fig 1: Input Graph (Weighted and Connected)

Given the above weighted and connected graph and source vertex s, following steps are used for finding the tree representing shortest path between s and all other vertices-

Step 1- Set dist[s]=0, S=ϕ // u is the source vertex and S is a 1-D array having all the visited vertices

Step 2- For all nodes v except s, set dist[v]= ∞

Set of visited vertices (S) S A B C D
0

Fig 2: Graph after initializing dist[]

Step B- a)Choose the source vertex s as dist[s] is minimum and s is not in S.

Step 3- find q not in S such that dist[q] is minimum // vertex should not be visited

Visit s by adding it to S

Step 4- add q to S // add vertex q to S since it has now been visited

Step c) For all adjacent vertices of s which have not been visited yet (are not in S) i.e A and C, update the distance array using the following steps of algorithm -

Step 5- update dist[r] for all r adjacent to q such that r is not in S //vertex r should not be visited dist[r]=min(dist[r], dist[q]+cost[q][r]) //Greedy and Dynamic approach

dist[A]= min(dist[A], dist[s]+cost(s, A)) = min(∞, 0+9) = 9
dist[C] = min(dist[C], dist[s]+cost(s, C)) = min(∞, 0+5) = 5

Thus dist[] gets updated as follows-

Set of visited vertices (S) S A B C D
[s] 0 9 5

  1. Choosing and visiting vertex C since it has not been visited (not in S) and dist[C] is minimum
  2. Updating the distance array for adjacent vertices of C i.e. A, B and D

Step 6- Repeat Steps 3 to 5 until all the nodes are in S

dist[A]=min(dist[A], dist[C]+cost(C,A)) = min(9, 5+2)= 7

dist[B]= min(dist[B], dist[C]+cost(C,B)) = min(∞, 5+9)= 14

dist[D]= min(dist[D], dist[C]+cost(C,D))= min((∞,5+4)=9

This updates dist[] as follows-

Set of visited vertices (S) S A B C D
[s] 0 9 5
[s,C] 0 7 14 5 9

Continuing on similar lines, Step B gets repeated till all the vertices are visited (added to S). dist[] also gets updated in every iteration, resulting in the following –

Set of visited vertices (S) S A B C D
[s] 0 9 5
[s,C] 0 7 14 5 9
[s, C, A] 0 7 8 5 9
[s, C, A, B] 0 7 8 5 9
[s, C, A, B, D] 0 7 8 5 9

The last updation of dist[] gives the shortest path values from s to all other vertices

The resultant shortest path spanning tree for the given graph is as follows-

Fig 3: Shortest path spanning tree

  • There can be multiple shortest path spanning trees for the same graph depending on the source vertex

Following is the C++ implementation for Dijkstra’s Algorithm

Note :
The algorithm can be mapped to any programming language as per the requirement.

The program is executed using same input graph as in Fig.1.This will help in verifying the resultant solution set with actual output.

Fig 4: Output

Time Complexity Analysis-

Following are the cases for calculating the time complexity of Dijkstra’s Algorithm-

  • Case1- When graph G is represented using an adjacency matrix -This scenario is implemented in the above C++ based program. Since the implementation contains two nested for loops, each of complexity O(n), the complexity of Dijkstra’s algorithm is O(n2). Please note that n here refers to total number of vertices in the given graph
  • Case 2- When graph G is represented using an adjacency list - The time complexity, in this scenario reduces to O(|E| + |V| log |V|) where |E|represents number of edges and |V| represents number of vertices in the graph

Disadvantages of Dijkstra’s Algorithm-

Dijkstra’s Algorithm cannot obtain correct shortest path(s)with weighted graphs having negative edges. Let’s consider the following example to explain this scenario-

Fig 5: Weighted graph with negative edges

Choosing source vertex as A, the algorithm works as follows-

Step A- Initialize the distance array (dist)-

Set of visited vertices (S) A B C D
0

Step B- Choose vertex A as dist[A] is minimum and A is not in S. Visit A and add it to S. For all adjacent vertices of A which have not been visited yet (are not in S) i.e C, B and D, update the distance array

dist[C]= min(dist[C], dist[A]+cost(A, C)) = min(∞, 0+0) = 0

dist[B] = min(dist[B], dist[A]+cost(A, B)) = min(∞, 0+1) = 1

dist[D]= min(dist[D], dist[A]+cost(A, D)) = min(∞, 0+99) = 99

Thus dist[] gets updated as follows-

Set of visited vertices (S) A B C D
[A] 0 1 0 99

Step C- Repeat Step B by

  1. Choosing and visiting vertex C since it has not been visited (not in S) and dist[C] is minimum
  2. The distance array does not get updated since there are no adjacent vertices of C

Continuing on similar lines, Step B gets repeated till all the vertices are visited (added to S). dist[] also gets updated in every iteration, resulting in the following –

Set of visited vertices (S) A B C D
[A] 0 1 0 99
[A, C] 0 1 0 99
[A, C, B] 0 1 0 99
[A, C, B, D] 0 1 0 99

Thus, following are the shortest distances from A to B, C and D-

But these values are not correct, since we can have another path from A to C, A->D->B->C having total cost= -200 which is smaller than 0. This happens because once a vertex is visited and is added to the set S, it is never “looked back” again. Thus, Dijkstra’s algorithm does not try to find a shorter path to the vertices which have already been added to S.


Recommended: Please try your approach on first, before moving on to the solution.

This article is contributed by Sahil Chhabra. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to [email protected] See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don&rsquot stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.

In case you wish to attend live classes with industry experts, please refer DSA Live Classes


Watch the video: Leap Motion SDK (September 2021).