Random Path Routing Network Using Colored Petri Nets

Random Path Routing Network Using Colored Petri Nets: History

Please note this is an old version of this entry, which may differ significantly from the current revision.

Subjects: Biochemical Research Methods

Contributor:

Wireless sensor networks (WSNs) have been applied in networking devices, and a new problem has emerged called source-location privacy (SLP) in critical security systems. In wireless sensor networks, hiding the location of the source node from the hackers is known as SLP. The WSNs have limited battery capacity and low computational ability. Many state-of-the-art protocols have been proposed to address the SLP problems and other problems such as limited battery capacity and low computational power. One of the popular protocols is random path routing (RPR), and in random path routing, the system keeps sending the message randomly along all the possible paths from a source node to a sink node irrespective of the path’s distance. The problem arises when the system keeps sending a message via the longest route, resulting because of high battery usage and computational costs.

wireless sensor network
source-location privacy
calculated random path routing
modeling
Petri nets

1. Introduction

One of the major wireless sensor network (WSN) deployment problems is source-location privacy (SPL) [1]. SLP includes the hiding of all source nodes in the network from attackers [1]. All the nodes are present in an open environment, and all the nodes are sending tokens from a source node to a sink node, so if attackers locate the source node, then the source node is at high risk. Providing privacy in sensor networks is very complicated because the nodes have low battery capacity and less computational power [2].

Previous studies have proposed numerous protocols to address SPL, and one of the fundamental protocols is random path routing (RPR) [4]. RPR is used to protect tokens from malicious attackers in the adversary [5]. RPR ensures SLP, however, it is expensive when it starts sending tickets along the longest path each time.

The proposed calculated random path routing (CRPR) model provides significantly better results in token routing. The proposed module’s distance calculation is our contribution. The system first calculates the distances of all available paths, and then randomly routes the token to any of the top three shortest paths. In other words, the model first calculates all the reaches of the known way and determines the shortest path, ensuring the SLP has a low computational cost and lower battery consumption. Additionally, it includes the formal modeling and verification of the CRPR, which authenticates the best tradeoff between computational cost and source-location privacy. The platform used for formal modeling is Colored Petri nets.

2. The CRPR model

Figure 1 shows the proposed methodology of the model. The CPN tool is used to formally model in the model. The token from a source node to the destination node is sent by using calculated random path routing. First, the model has to find all the possible available paths to send the packet from source to destination. The model has traversed all the possible nodes of that path and gets the calculated path distance. Before sending the packet to the network, the model has all the routes from the source node to the sink node. Now the model has the choice to send the packet from either the shortest path or longest path. It depends upon the token to be sent. The model can send the message from the shortest path again and again if the message does not contain critical information.

Figure 1. Proposed model.

WSN is used to monitor sound, temperature, pressure, etc. Most source nodes are exposed to the cyber city, so source-location privacy (SLP) is necessary [23]. Separate path routing or multi-path routing are protocols that are used in SLP [24]. Separate path routing or multi-path routing is used to secure the location of the source node while sending the message from a source node to a sink node, but it is computationally expensive. To reduce the computational cost, the proposed modification of the current working protocol adds an additional feature is being added in this research to reduce the computational cost. SPR is computationally expensive when the longest path is selected to transfer data from a source node to a sink node. This computational cost can be minimized by first calculating the distances of all paths. After then selecting the top three shortest distances from all the distances and finally a section of one path from the top three shortest distances will decrease the computational cost.

3. Hieratical Colored Petri Nets

Hieratical Colored Petri nets define the abstract view of the model. It contains the sub-modules of the model. Each module is connected to the other modules and passes its values to the other modules. The hierarchal Petri net of the system is shown in Figure 2.

Figure 2. Hieratical Colored Petri Nets.

There are two sub-modules in the system.

Route finding
Token passing

3.1. Route Finding

The input for the route finding module is the empty list. The route finding module transverses all the routes one by one and calculates the distance between all routes, as shown in Figure 3. It generates a list that contains the calculated distance in integral form.

Figure 3. Root finding.

Token Passing: The input for the passing token module is the list of calculated paths’ distance. The token can be fired to any of the calculated distances, and the distance of the route would be already known.

Figure 4 below shows the transfer of data from a source node to a sink node. Here it can be seen the distance between the nodes. There is more than one path for packets to go from source to destination. A problem arises when the system selects the longest paths again and again, causing an increase in the computational cost.

Figure 4. Token passing.

3.2. Token Passing

There are two equations utilized for token passing shown below as follows:

Pin (path routing) = [] (Pin input for the module, and [] is the empty list)
Pout (calculated distance) = [list of all paths distance] (Pout is the module’s output that contains paths distance)

The above equations show that the input for this module’s route finding is the list of the calculated distances from a source node to a sink node. When the token is passed through the source node to the sink node, it follows the same path provided by the route-finding module in Figure 4, token passing.

4. Comparison of CRPR with Other Similar Routing Techniques

The comparison of the proposed CRPR model with other similar routing techniques is shown in Table 3. The phantom routing-based techniques are not formally modeled by Petri nets, and it also does not use any guard value. It is a single-path routing scheme, and it can have repetitive packets sent. The fake source-based techniques are also not modeled yet, and it is a multi-path routing technique. Dynamic source routing is a secure network technique, but not formally modeled yet, and it is a multi-path routing technique. Associativity-based routing is also not modeled yet, and it is a multi-path routing scheme. Our proposed technique models the shortest selective random path routing technique and is formally modeled by using the guard technique. SSRPR is a multi-path outing scheme and its reachability is 100%. However, this model does not have a liveness property. The comparison of the proposed model with the existing techniques shows relatively good results so far as the security of the packets is concerned.

Table 3. Comparison of CRPR with other similar routing techniques.

Protocol	Formally Modeled	Guard Checking	Multi-Path Routing	Reachability	Liveness
Phantom routing-based Techniques	NO	NO	NO	YES	YES
Fake sources-based Techniques	NO	NO	YES	YES	YES
Dynamic Source routing	NO	YES	YES	NO	YES
Associativity- based routing	NO	NO	YES	YES	NO
Dynamic backup routes routing protocol	YES	NO	YES	NO	YES
Hint-based probabilistic protocol	NO	NO	YES	NO	NO
Shortest selective random path routing	YES	YES	YES	YES	YES

5. Conclusions

Source-location privacy is an essential issue in routing protocols. With the invention of new and critical information transmission methods, the safe transmission of data is a critical issue. Routing protocols have managed to solve this problem, but there is always a margin for improvement. The model presented is our best attempt to give positive input to solve this problem by improving the already existing random path routing protocol and naming it Calculated Random Path Routing (CRPR). The model considers the tradeoff between privacy and computational cost to improve the existing routing protocol.

This entry is adapted from the peer-reviewed paper 10.3390/app12031426

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.