Loading menu…

FREE HIT A Novel History based Reinforcement Approach for Fast Path Construction in Vehicular Ad hoc Networks

Β§ Sri Venkateswara University College of Engineering,T...
‑ Sree Vidyanikethan Engineering College

Send Message

To: Author

FREE HIT  A Novel History based Reinforcement Approach for Fast Path Construction in Vehicular Ad hoc Networks

Article Fingerprint

ReserarchID

Q93X7

FREE HIT  A Novel History based Reinforcement Approach for Fast Path Construction in Vehicular Ad hoc Networks Banner

Key Research Insights

Synthesized scholarly intelligence & interactive research assistant
  • English
  • Afrikaans
  • Albanian
  • Amharic
  • Arabic
  • Armenian
  • Azerbaijani
  • Basque
  • Belarusian
  • Bengali
  • Bosnian
  • Bulgarian
  • Catalan
  • Cebuano
  • Chichewa
  • Chinese (Simplified)
  • Chinese (Traditional)
  • Corsican
  • Croatian
  • Czech
  • Danish
  • Dutch
  • Esperanto
  • Estonian
  • Filipino
  • Finnish
  • French
  • Frisian
  • Galician
  • Georgian
  • German
  • Greek
  • Gujarati
  • Haitian Creole
  • Hausa
  • Hawaiian
  • Hebrew
  • Hindi
  • Hmong
  • Hungarian
  • Icelandic
  • Igbo
  • Indonesian
  • Irish
  • Italian
  • Japanese
  • Javanese
  • Kannada
  • Kazakh
  • Khmer
  • Korean
  • Kurdish (Kurmanji)
  • Kyrgyz
  • Lao
  • Latin
  • Latvian
  • Lithuanian
  • Luxembourgish
  • Macedonian
  • Malagasy
  • Malay
  • Malayalam
  • Maltese
  • Maori
  • Marathi
  • Mongolian
  • Myanmar (Burmese)
  • Nepali
  • Norwegian
  • Pashto
  • Persian
  • Polish
  • Portuguese
  • Punjabi
  • Romanian
  • Russian
  • Samoan
  • Scots Gaelic
  • Serbian
  • Sesotho
  • Shona
  • Sindhi
  • Sinhala
  • Slovak
  • Slovenian
  • Somali
  • Spanish
  • Sundanese
  • Swahili
  • Swedish
  • Tajik
  • Tamil
  • Telugu
  • Thai
  • Turkish
  • Ukrainian
  • Urdu
  • Uzbek
  • Vietnamese
  • Welsh
  • Xhosa
  • Yiddish
  • Yoruba
  • Zulu
Reading Preferences
Font Size
Line Spacing
Background
This converted HTML version may contain rendering inconsistencies. Please refer to the PDF for the authoritative version, or click here to provide feedback.

Abstract

Vehicular ad hoc networks playing significant role in development of intelligent transport system and rise in demand for accessing fascinated applications such as entertainment and advertisements in vehicles via internet leverages to build efficient routing mechanisms. Due to rapid vehicles flow in Vanets, network often subjected to link breaks and creates delay in communication which affects overall network performance, hence to address these serious issue earlier approaches focused on parameters like rate estimation, feedback and link-expiration-time but being different from earlier our Instant Look up and Immediate Action(ILU-IA) technique uses adaptive learning thru past knowledge. ILU-IA identifies immediate neighbour (Free-Hit-Node) efficiently at point of link failure using Case- Based-Learning and Q-learning techniques. Simulation analysis shows that proposed approach performance improved in terms of throughput with negligible delay also reduces network overhead.

I. INTRODUCTION

Vanets [1],[2] comprise of vehicles and road side units which offer direct information exchanges between vehicles and vehicles to and from RSU and exchanges information like current traffic and sharing high priority messages using dedicated short range protocol for communication. Now a day's vehicle on road increases phenomenally and creates more difficulty to handle all vehicles under single point of control to address this issue one way is to use hierarchical topology where vehicles are grouped into clusters and one cluster head is elected to manage group members as shown in fig 1. For inter cluster communication Cluster Head(CH) selects one node in group to act as gateway and considerable amount of work has been carried out for cluster creation, maintenance and knowledge sharing [3],[4] and clusters are internally connected to road side units in order to exchange information between clusters as well as RSUs.In existing to establish reliable routing Hashem & Owens [5] proposed SAMQ algorithm which provides routing reliability by make use of "situation awareness", routing decisions would be taken only after comprehensive analysis of current traffic patterns with stored patterns, then suitable actions will be taken to revive situation additionally SAMQ utilizes ant colony system algorithm for searching feasible paths.

Fig. 1: Vanets Cluster Architecture
Fig. 1: Vanets Cluster Architecture

In other existing approaches [6],[7] whenever link failure occurs control signals were used to search new node or block to forward packet towards destination which increases network overhead. In another research [8] buffering technique used to store packets temporarily until new path traced out or source initiates [9] a new path from beginning again in all above approaches RREQ flooding and ACK signals were required to find new node which wastes network bandwidth here point to be consider that vanets are delay sensitive networks, sure it would consume some amount of valuable network time to search new neighbour node, assigning addresses and diverting packets results in delay. To overcome aforementioned issues in proposed system cluster head collects and sends various traffic situations information like number of vehicles in clusters their velocities, moving direction and positions etc. along with above information CH maps traffic patterns to Intelligent road side units (IRSU). Initially Cluster Heads sends collected traffic patterns to repository later CBL and Q-learning algorithms applied for machine learning. In this paper our intention is to reduce network overhead and delay by applying "instant look up and immediate action" from past experiences, section-II shows state-of-art while section-III describes methodology and algorithms, section-IV shows performance evaluation and section-V concludes the work

II. STATE-OF-ART

In research [10] fuzzy logic and rate-estimation-algorithm used for finding reliable path between source and destination. Fuzzy logic is used select straight link and mostly applied to real time applications where information about things is not accurate. It uses linguistic terms to define the facts while Q-learning algorithm adjusts behavior of nodes using trial and error base. Q-Table dynamically updates its contents like action and state of vehicle environment by agent. Whenever changes occur in states immediately the same should mirror in Q-Table otherwise learning data is unused. Transfer learning is used to apply learned knowledge to another similar environment, so that decision making would be ease and faster for new arriving nodes. Finally to find reliable end to end path both route selection and rate estimation process were used. In [11] to enhance optimized link state routing author combined four metaheuristics techniques to achieve automatic optimization process. Simulated annealing for finding global best solutions to given function. Genetic algorithm (Panmictic & decentralized) used here to solve multicast routing issues also identifies best selections based on minimum time factor in local optima, particle swarm optimization at global level calculates second minimum shortest time using differential evaluation for efficient resource scheduling to minimize packet loss ratio. In[12] vehicles are grouped thru velocities so that assumption is all moving with same pace therefore stability also high. ROMSGP technique gathers group information based on Link-Expiration-Time, Stable link selections based on expiration time i.e. Long LET, whenever path goes down immediately RERR message would send to source node. One alternate is choosing next best path without link breakages accordingly routing table is then modified and another solution if there is no alternate path from break point source again initiates route discovery if no of hops from source to break point is minimum otherwise local recovery process will be initiated. So here usage of control messages were minimized and reduced communication delay but gathering vehicles with same speed, calculating LET and route discovery process would increase in more computational complexity which may not suitable for dynamic networks like Vanets. In [13] automatic rate fall back (ARF) periodically sends probes with different speed rates i.e. lower rate and higher rate, if it faces more continuous packet loss in either cases based on minimum losses it may choose higher or lower speeds but would not suitable for dynamic networks. Sample rate initially sends data with maximum rates based and based on failures (more than four packet losses) it stops sending and then chooses another rate at which capable of forwarding packets.

This technique stores total information like number of transmissions, success ratios, failure details and timings, for further transmissions algorithm analysis history stored in table and chooses best rate to accomplish maximum throughput. In research [14] Reinforcement learning (RL) is used to acquire knowledge of given space by observing behavior in order to improve machine intelligence. Combinatorial – optimization- problems (COPs) such as limited resources allocation for more requirements and dynamic search space where hard to find optimal possibilities. Distributed RL (DRL) is used for solving COPs in a simple way like what-to-do and how to map discovered states to actions, here agent selects actions based on feedback from earlier states and actions. The agent intent is to collect and summarize feedback received from initial ceremonial to final state so that machine could precisely take decisions for further created search space. In [15] Q-learning is used with AODV where all the node entries in Q-table contains distance and next hop information i.e. Q(d,x) values ranging from 0 to 1 whereas dynamic Q-table size depends on number of neighbour and destination nodes. Table information and learning information distributed to all neighbors. QL-AODV used dynamic routing to avoid route and link breaks to attain maximum throughput also without delay revives path with current track of information.

Collaborative feedback learning [16] used to give optimization solutions by analyzing information from multiple agents. In CRL an isolated agents monitors system states and continuously updates gathered information to optimal policy table maintained by agents and based on this feedback learning decisions would be taken and Markov processes used to model feedback (reinforce) learning problems and SAMPLE algorithm tunes with changing scenarios dynamically to maximize throughput. Minimum-delay-routing algorithm [17] uses two-ways of vehicles in cluster to forward message from source to destination. MDRA technique applied to identify end to end path with minimum delay and epidemic routing is used to avoid duplicate packets such that cluster contains single-copy of message. To find distance between vehicles author used probability distribution function for message forwarding process, Markov-renewal technique and dijkstra's algorithm is used to find reliable and optimal path with less delay. In [18] VOEG -VANET oriented Evolving graph paradigm used prediction algorithm to find vehicles at particular instant and EG-dijkstra's (Evolving- Graph) technique is used to find reliable path and reliable graph[RG] array stores overall vehicle information so that whenever path is required then RG generates most optimal and reliable routes. If the link is not there in between two nodes i.e. reliability equals to zero then VOEG verifies current traffic conditions and adjusted to new node to attain journey reliability using graph information which avoids route requesting process but graph based approach well suited for static or slow speed networks. In MOZO [19] for decision making a captain node is elected and cluster members for each cluster also named as zones to forward packets form source to destination. Dijkstra's procedure to compute the shortest path and for zone formation moving object modeling and indexing techniques were used. CLV-Tree algorithm calculates and maintains similar vehicles information (velocity, direction, position).

Fig. 2: Moving zone based protocol model
Fig. 2: Moving zone based protocol model

VADD [20] supports multi hop data forwarding using carry and forward technique particularly for sparse area networks whenever node carrying packets notable find path then node simply carries packets until next node comes to availability. VADD uses Directed Graph to represent vehicular network and Dijkstra's method to compute shortest path basic idea is to reduce forwarding distance without loops for that purpose author designed H-VADD. In [21] Node rotation concept is used here for increase network lifetime so the power consumption of all the nodes would be equally utilized. Repeated-optimal-matching used to make multiple rounds to identify nodes that are optimally matched and gathers local information from other nodes like energy, position and load. Consumption-swap-rate-algorithm swaps only the nodes at high rate consumption positions. Energy level swap used for nodes which come down below threshold energy point.

In [5] SAMQ initially gets complete insight of vehicular network like locations, velocities, traffic information, behavior of drivers and environmental conditions etc. Current situation of network could be analyzed by using gathered information. With precise information routing algorithms estimates link life time between nodes i.e. reliability of link and last appropriate actions will be taken to discover path between two nodes in case of current link failure. SAMQ uses Ant-Colony-System algorithm to build optimization solutions with three common rules Pheromone deposit, State Transition and Pheromone evaporation.

Fig. 3: SMAQ Model
Fig. 3: SMAQ Model

It aims to select reliable path among alternatives proactively rules pheromone deposit, State Transition and pheromone evaporation. Motivation for our proposed drawn from SAMQ technique.

III. GLIMPSE OF PROPOSED SYSTEM

a) Instant Look up –Immediate Action (ILU-IA)

  1. Intelligent RSU's (IRSU) Collects clusters state information i.e. number of vehicles, positions, directions and link failures points at various traffic situations and reliable path links and stores in repository server.

  2. Later Case Based Learning and Q-learning algorithms applied on stored data for Learning.

  3. All cluster head maps their current traffic patterns to IRSU's, instantly IRSU picks information from server and sends corresponding data like expected failure points and reliable links etc. to cluster heads.

  4. Using past information cluster head can anticipate where exactly link failures could occur in particular traffic pattern then immediately locates a position nearer to failure point and temporarily allocates a node called free hit node (FHN) to handover packets for smooth communication.

IV. SYSTEM MODEL

Cluster Maintenance In general Cluster comprises of Cluster Head (CH) also Cognitive node which is responsible for cluster maintenance and Cluster Members (CMs) used to carry and forward packets and one gateway node for inter cluster communication along with above nodes proposed solution maintains two significant nodes called:

1. Free Hit Node (FHN).

Intelligent Road side Units: We assume that all clusters are connected to set of road side units (RSU's) in turn RSU's are connected to main server. Initially RSU, s collects live traffic information from clusters and updates same in main server also shares information between clusters.

Repository Server: Graph structures are used to store traffic patterns in repository later machine learning algorithms are applied to train server, once current traffic pattern matches with stored pattern then essential feedback will send cluster head to manage situations such as link failure points and reliable paths patterns.

Handling Link breaks: Cluster Head knows concise traffic information bit early with the use of it CH identifies and temporarily reserves a special node which is labeled as FREE HIT NODE (FHN) nearer to position where link break might occur and FHN cannot be used by another task except waits to get connect with node at link failure point and CH adds necessary information like FHN address to data packets and also stores path details in FHN from point of failure.

Node Rotation: Proposed uses the node rotation[21]concept for efficient utilization of failure nodes because whenever a link break arises, CH diverts packets to a Free-Hit-Node from the point of failure for sending packets towards the destination. But here, recently link-failed node (RFN) becomes free from usage at a particular situation, so in order to rehash RFN, we used node rotation so that later RFN could be used as FHN or co-operative node. Vanet Mobility Model:

To epitomize VANETs, proposed system uses graphs where vehicles and links can be showed as vertices and edges and below fig shows grid graph modeling used to represent cluster type of networks.

Fig. 4: Grid graph
Fig. 4: Grid graph

Gross area (GA) = > gross length and gross width of the graph and assuming all nodes are communication under same radio frequencies R.

C Max Graph β–‘ Maximum graph walk coverage with set of edges E and I(e) is length of edge e. Cmaxg approximately equals to sum of all edges multiplied with radio frequency range diameter [22].this equation suitable for short ranges like cluster based networks.

CMAX=βˆ‘l(e)βˆ—2RebelongstoE
Fig. 5: shows graph representation
Fig. 5: shows graph representation

Intelligent RSU (IRSU) collects live traffic information from cluster head and forwards to server, initially all the patterns allowed to store into repository later server discards if similar pattern arises.

IRSU explores state of link failures and reliable paths i.e. in certain traffic pattern- speed of vehicle, position, direction, and link status and active information (link failure patterns & reliable paths) etc. later information pushed into repository server.

Fig. 6: Link failure situation
Fig. 6: Link failure situation

V. ALGORITHMS

Case-Based Learning for Attribute Graphs

CBL algorithms [23],[24] basic feature is to extract re-usable cases which have relevant structures to the new patterns and uses hierarchical decision trees tot stores graph attributes so that information retrieval becomes simple and fast. Initially CBL stores all traffic patterns knowledge and rehash the information obtained to new similar patterns from previous quality solutions, generally instance based learning models applied to solve tasks like real valued functions, in proposed case-based-reasoning (CBR) algorithm used to match complex traffic pattern instances also for efficient indexing to extract matched patterns and this model usually collect and store traffic patterns in database and compares new traffic patterns with stored ones to find best fit match and immediately pushes pattern state to Q-learning module for necessary actions to avoid link failures fig.6 Case based learning and Q-learning framework.

Fig. 7: Case Based Learning & Q-Learning Frame work
Fig. 7: Case Based Learning & Q-Learning Frame work

Q-learning Algorithm to locate Free Hit Node

Q-Learning [25] is kind of reinforcement process used to estimate the values of state and action pairs i.e.

For each step "s" "selects action "a" which maximizes fun Q(s, a) Where Q→ estimated function s → State a → Action.

In proposed Q (traffic patterns states, actions)β†’ action specifies where to place "FHN" for corresponding traffic pattern.

Fig. 8: Free hit node Q-Learning Process
Fig. 8: Free hit node Q-Learning Process

Initialize Q (tps, a) randomly While (For Each Traffic Pattern State stored in Q-table derived from CBL)

{ IF (Current state matched) THEN If there is no failure points then Q (TPS, a) β†’ c + Q (TPS, Null); // action = Null; Else Q (Pattern, a) β†’ Q (TPS, action β†’ Link Break point, FHN (nn) //adds link break points and predicts optimal neighbour node End if; END IF; }

VI. EXPERIMENTAL SETTING AND PERFORMANCE ANALYSIS

This section demonstrates our ILU–IA features improved in terms of reducing end to end delay, minimizes packet drop ratio and reduces time taken to find neighbour node when compared with existing approaches. The vehicular traffic is generated using network simulator with some initial values like 40m/sec speed; each cluster comprises maximum 10 vehicles, acceleration values -7 to 7m/s2 and rate of data packets 15packets/sec. Performance evaluation factors:-

Routing overhead: In proposed system total number of control messages for finding new node almost negligible because our history based prediction approach straight way expects and places free hit node (FHN) nearer to failure.

Fig. 7: Network over head
Fig. 7: Network over head

Packet drop ratio: Due to dynamic decision making nature of ILU-IA approach, link failures can efficiently handle by cluster head therefore reduces packet drop ratio between vehicles.

Fig. 8: Packet delivery ratio
Fig. 8: Packet delivery ratio

Transmission delay: aforementioned parameters are directly reflects delay, in our proposed approach both routing overhead and packet drop ratios minimized. Hence end to end delay also reduced.

Fig. 9: Transmission delay
Fig. 9: Transmission delay

VII. CONCLUSION

In this research we introduced innovative solution to construct fast path restoration in cluster based vehicular networks. The main objective behind ILU-IA protocol is that instead of looking for new neighbour node after link break, which in turn produces more delay and packet drops. Our proposed system uses past experiences or history to handle any kind of situation efficiently here cluster head could able to foresee entire behavior of current network with information obtained from IRSU like expected failure points, packet drop points etc. so proactively cluster head selects alternative nodes nearer to failure points. Simulation analysis shows ILU-IA outstanding performance in terms accomplishing high throughput and increase in overall network performance.

Funding

No external funding was declared for this work.

Conflict of Interest

The authors declare no conflict of interest.

Ethical Approval

No ethics committee approval was required for this article type.

Data Availability

Not applicable for this article.

How to Cite This Article

Abhilash Kumar Reddy Manchu, A.Rama Mohan Reddy. 2017. "FREE HIT A Novel History based Reinforcement Approach for Fast Path Construction in Vehicular Ad hoc Networks". Global Journal of Computer Science and Technology - E: Network, Web & Security GJCST-E Volume 17 (GJCST Volume 17 Issue E4).

More Citation Formats

Download Citation

Journal Specifications

Crossref Journal DOI 10.17406/gjcst

Print ISSN 0975-4350

e-ISSN 0975-4172

Keywords
Classification
C.2.1
G.2.2
Version of record
v1.2

Issue date
September 27, 2017

Language
English
Order Article Reprint
Experience in AR

Explore published articles in an immersive Augmented Reality environment. Our platform converts research papers into interactive 3D books, allowing readers to view and interact with content using AR and VR compatible devices.

Read in 3D

Your published article is automatically converted into a realistic 3D book. Flip through pages and read research papers in a more engaging and interactive format.

Article Matrices
Total Views: 1.4K
Total Downloads: 61
All Trends

This is the heading

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

High-quality academic research articles on global topics and journals.

FREE HIT A Novel History based Reinforcement Approach for Fast Path Construction in Vehicular Ad hoc Networks

Abhilash Manchu
Abhilash Manchu Sri Venkateswara University College of Engineering,Tirupati.
A.Rama Reddy
A.Rama Reddy <p>Sree Vidyanikethan Engineering College</p>

Request Access

Please fill out the form below to request access to this research paper. Your request will be reviewed by the editorial or author team.
X