Link State Hop-Hop Routing for CV2S

Link State Hop-Hop Routing for CV2S

Amrit Rajeev

BTech Student, PES University India

Dr. Sandhia Valsala Asst Professor

University of Buraimi,Oman

AbstractTraffic congestion is now an inescapable condition faced by all growing cities around the world. In todays world people are accustomed to living in such conditions. With the increasing number of vehicles in countries across the world, the density of vehicles on road increases resulting in increased travel time. The solution to this is to optimize the route one takes. With all major cities having a network of traffic signals the path taken by the vehicle can be optimized. Data generated from cameras attached to the signal are to be analyzed in finding the optimal path. This paper looks to take advantage of the comparability between road network and computer network thus finding an effective solution to traffic congestion problem by generating an optimal path that takes less commutation time. Traffic congestion can be a major setback for smart vehicular navigation. This paper proposes how linked state routing approach can be modelled in a simulated traffic network and its implementation for smart vehicles navigation

Keywords Traffic Congestion; Optimal Path; Road Network; Link State Routing

1. INTRODUCTION

   Passenger vehicular sales have drastically increased over the years [1] and is projected to grow in the coming years. With automobiles industries set to flourish [2] in the coming years the infrastructure should also evolve to keep up with the surge. Population being a key factor in traffic density and it directly being affected by the country's growing economy

   [3] finding a way to manage the traffic effectively becomes the key. Traffic congestion occurs when the road infrastructure is unable to handle the number of vehicles on the road. This is a common occurrence in almost all metropolitan cities, especially true in developing countries with poor infrastructure.

   During an average trip one spends a considerable amount of time stuck in traffic and once it turns green, they end up taking a route with more vehicle density and spend more time waiting. Smart car navigation in signals is more challenging as suboptimal path selection probability increases.

   Smart cars are the future of vehicular transportation. The proposed work will be prominent with emerging technologies like Cellular vehicle-to-everything (CV2X). CV2X uses 4G or 5G to send and receive signals from other vehicles/environment. A subset of CV2X being Cellular vehicle-to-signal (CV2S) communication in which the vehicle can send and receive information from the signal will be used as the base theory in this paper. The information provided, will assist the vehicles navigation in an optimal path to reduce delay. Self-Driving cars will also be able to

   take advantage of this model by being able to seamlessly navigate through high traffic regions.

   Since Link State routing is one of the most promising routing protocols in computer networks [9] it can be modelled for a traffic network. Using the proposed model, which is further optimized in [11], the vehicle can be provided real time data of traffic which will assist in deciding the optimal path. The vehicle density is dynamic in nature thus creating varying efficient paths in the network. The vehicles current signal position will be assigned as the source node of the model and by setting the desired destination as the end node, the path with least density can be found. Cars can be given access to the routing table at the signal as smart cars can be easily integrated with the signals. This will provide the cars information about the non-line of sight traffic congestions.

   The proposed work will be prominent with emerging technologies like Cellular vehicle-to-everything (CV2X). Cars can be given access to the routing table at the signal as smart cars will be able to communicate with the environment. A dedicated short-range communication (DSRC) protocol which is a one or two way short-range wireless communication will be set up between the cars and the traffic signal. This will help the vehicles navigate in an optimal path to reduce travel delay.

2. RELATED STUDY

   Smart car navigation has gained traction over past years as congestion keeps increasing, various models have been developed as a solution. The proposed model is advantageous because of its high scalability and reliability. After adaptations, the Link state protocol has been worked and modified to meet the challenged faces. Some of the other methods proposed are:

   1. Smart Car with Electromagnetic Runway

      Electromagnetic Runway works on the principle of the car following a fixed strict path. The direction of the intelligent car control is realized through controlling the steering gear by Pulse Width Modulated (PWM) wave. Steering gear is controlled through the cycle of fixed pulse signal control, the steering gear indexing is proportional to the pulse width, and the continuous pulse signal can be realized by the PWM. Steering gear inside will generate a reference signal frequency which is 50 Hz. In order to determine the size of the steering and corner reference signal, the given PWM wave is compared with external

      pulse duration. Motor adopts the classical Proportional- Integral-Derivative(PID) control. This paper provides a base for vehicular navigation using a strict path, this requires high infrastructure needs and cost for set up.[4]

   2. RFID based smart traffic management

      Each vehicle can be installed with a Radio-Frequency Identification(RFID) tag. These RFID tags would store all the information regarding the vehicle such as the vehicle number, etc. RFID tags can be used in identifying each vehicle uniquely and helps the driver to receive some traffic messages. The existing signalling system can be coupled with the RFID controller. Each signal can have the information regarding every vehicle that passes by it. Thus, when a vehicle passes by a signal, the signal can automatically keep the count of the vehicles passing by it, and help in detection of traffic congestion. The installation of RFID on every vehicle will be expensive and the cost of installation would likely be very heavy on the consumer. The RFID may lead to false detection of signals which leads to problems while computing the optimal path. [5]

   3. Inductive Loop

      Inductive loop detection works on the principle that one or more turns of insulated wire are placed in a shallow cut-out in the roadway, a lead in wire runs from roadside pull box to the controller and to the electronic unit located in the controller cabinet. When a vehicle passes over the loop or stops, the induction of the wire is changed. Due to change in induction, there is change in the frequency. This change in the frequency causes the electronic unit to send a signal to the controller; indicating the presence of the vehicle. To implement this system roads existing roads have to be dug up and if executed in an incorrect way will lead to inconvenience. The model will be difficult to implement in a narrow road as digging up the road will lead to non- functioning of the road. [6]

   4. Time constrained Shortest Path

   The shortest path algorithm of time complexity O (r – n3) is developed, where n denotes the number of nodes in the network and r the number of different windows in a node. This model uses multiple timeframes and, in each time window, only a specific route is turned green for the vehicles to pass. The node-based methodology will be adapted and optimized further as te shortest path need not be the most optimal in the real-world scenario [7].

3. PROPOSED MODEL

   In the city map with multiple traffic signal intersections, considering each traffic signal to be the node we get an interconnection of network [7]. Assuming a n nodded road network with r optimal routes. The commuter can then set one of the n nodes as the destination and the present node will be set as source by default. By using the array of surveillance cameras present at each of the n signals we

   capture n images. Since the cameras placed already in the signals are at an angle that they cover a decent distance of the lane hence the images will give a good indication of the number of vehicles. This image is sent to a computing device where the algorithm will localize all the vehicles in the images. Counting the number of boxes will give the approximate number of vehicles on that lane. By taking into account the distance between the present and next node along with the number of vehicles, a weight is assigned to that path which will be its density. The weight estimate is given by:

   This weight information of adjacent nodes will be stored in the link state table for each node. By finding the path least weight will give the most optimal path through traffic signals. The computation of least weight path can be done by applying the equation for the constraint:

   The above is known as the Bellman-Ford Equation. The optimal path would be the route r which has the least accumulated density between the set source and destination. Updating of weights is done every time the signal turns red thus keeping the values real time. With each node able to access the state of the adjacent node, with this information the commuter will be able to take the most optimal path between source and destination. The source node is then updated to the next node which the commuter reaches. This can be repeated until the source and the set destination matches

   FIG. 1 WORK FLOW OF THE MODEL.

   This model will create a pavement for efficient traffic management by having the optimal density of vehicles at each signal which will make navigating through them more time efficient.

   Fig. 2 Sample Road network of a city

   Fig.2, taken from [10] shows correspondence between a road network and a computer network which justifies the use of link state routing for optimal traffic management. Over a large network of roads, it can be seen that the use of this method will drastically reduce the travel time.

4. IMPLEMENTATION AND RESULTS

   Fig.3 shows the network where the sample simulation will be done.

   Fig. 3 Road network between Source and Destination

   In the above network, each of the nodes will have 100 cars in route 1 , 50 cars in route 2, 75 cars in route3 in the initial time window. Each node will be half hour away (free road) and be 1Km away each by default. We have 5 nodes and 3 routes we can take between Source(S) and destination(D).

   Fig. 4 Distance vs Time without addition of the model

   From Fig.4, by taking a non-optimal route the max will take a total travel time of 90 mins and might even increase under different conditions. While the observation window is subject to changes, we can assume a linear relationship for ease of complexity. In the sample network the model is applied.

   Fig. 5 Distance vs Time after addition of the model

   From Fig.5, by taking into account the density and at each node the optimal route is selected by which the total time is roughly 70 mins which is 20 mins of a difference. This difference will become more evident in a real-world scenario where the variables of a dynamic environment will be taken into account.

   The model has been able to successfully pick the optimal path at each node. The above results validate the use of Hop-Hop based link state routing mechanism which will aid smart in smart vehicle navigation. Multiple models and modification are considered for the model and a new link state protocol, Penalizing Exponential Flow-splitting (PEFT) will be used based on [11].

   Emerging technologies like CV2-X will aid in Smart and self-driving vehicles navigation, which can be implemented by giving the vehicles access to the data of the link data table. In doing so it will make a self-organised navigation system by it being able to communicate to the environment.

   ACKNOWLEDGMENT

   I would like to extend my deep thanks to Dr.Sandhia for motivating me to publish this paper. Appreciate her constant guidance without which this paper wouldnt have taken this shape.

   REFERENCES

   Fig. 6 Comparison of PEFT on optimality

   Fig.6 from [11] shows that PEFT outperforms Open Shortest Path First (OSPF) in terms of optimality scalability and implementation. This model's performance will be tested on Figure [4] which shows the network where the sample simulation will be done. The vehicle should be able to identify the optimal form source to destination at each node it ends up reaching.

5. CONCLUSION

   The proposed method has an easy execution and scalability to meet the challenging scenario of the real world. Making it a prominent working model, with Link state routing protocol being used widely across the world it can no doubt be scaled to meet the requirement of this paper.

   The model outshines the existing methodologies in terms of its performance along with cheap cost and low infrastructure demands. The resourcefulness really comes with its ability to be integrated with current technologies like google maps and with its innate ability to aid in navigation of smart and self-driving cars.

6. FUTURE RESEARCH

Google maps is one of the primary tools to integrate the model with. With the maps already providing optimal paths between two locations, with integrating the proposed model google maps and optimize its route on signal level making it more efficient.

1. https://www.financialexpress.com/auto/car-news/passenger-vehicle- sales-up-11-car-sales-bike-sales-maruti-hyundai-hero-motocorp-tvs- bajaj-auto/2193163/

2. https://auto.economictimes.indiatimes.com/news/industry/budget- 2021-creates-highways-for-auto-sector-growth/80653230

3. Azeem Uddin, Draft, 23 March 2009. Traffic congestion in Indian cities: Challenges of a Rising power. http://www.visionwebsite.eu/UserFiles/File/filedascaricare/Scientifci

   %20Partners,Papers%28Kyoto%29/Draft_koc_Azeem%20Uddin.pdf

4. Qu, Juntao & Hou, Ming & Li, Linghui. (2013). Experimental Research and Analysis on Smart Car with Electromagnetic Runway. 10.2991/3ca-13.2013.113.

5. Lanke, Ninad & Koul, Sheetal. (2013). Smart Traffic Management System. International Journal of Computer Applications. 75. 19-22. 10.5120/13123-0473.

6. US7245220 B2. Jul 17, 2007. Radio frequency identification (RFID) controller. http://www.google.com/patents/US7245220

7. Javed Alam, Pandey MK , Design and Analysis of a Two Stage Traffic

8. Light System Using Fuzzy Logic ,J Inform Tech Softw Eng 5: 162, November 2015

9. Sripranav S., Ravi A., Gautham K., Leela Velusamy R. (2021) Smart Traffic Navigation System (STNS) to Reduce Travel Time by Integrating Signals from Navigation and Traffic Systems. In: Zhang YD., Senjyu T., SOIN C., Joshi A. (eds) Smart Trends in Computing and Communications: Proceedings of SmartCom 2020. Smart Innovation, Systems and Technologies, vol 182. Springer, Singapore. https://doi.org/10.1007/978-981-15-5224-3_10

10. Lakhmir, M & Qureshi, Ayaz & Channa, Muhammad & Jokhio, Fareed & Nizamani, Shahzaman. (2015). Performance Evaluation of Link State Routing Protocol in an Enterprise Network. BUJICT-Vol. 8, Issue 1, April 2015. 8.

11. Guo, S., Zhou, D., Fan, J. et al. Identifying the most influential roads based on traffic correlation networks. EPJ Data Sci. 8, 28 (2019). https://doi.org/10.1140/epjds/s13688-019-0207-7

.