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.
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.
  1. Route finding
  2. 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:
  1. Pin (path routing) = [] (Pin input for the module, and [] is the empty list)
  2. 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

This entry is offline, you can click here to edit this entry!
ScholarVision Creations