An unattended Cluster-based VANET-Oriented Evolving Graph Model and ATED Reliable Routing Theme

An unattended Cluster-based VANET-Oriented Evolving Graph Model and ATED Reliable Routing Theme

Ramya K1, Kubra Banu2, Harshitha M S3 , Kiran Y M4, Narasimha M R5

Assistant Professor, Dept. of ECE, BGS Institute of Technology, Mandya, Karnataka, India1 UG Student, Dept. of ECE, BGS Institute of Technology, Mandya, Karnataka, India 2, 3,4,6

Abstract:-In conveyance unexpected networks (VANETs), communication links break a lot of often because of the high- speed vehicles. during this paper, a completely unique cluster- based VANET directed evolving graph (CVoEG) model is projected by extending the present VoEG model to boost the responsibility of conveyance communications. Here, the link responsibility is employed as a criterion for cluster members (CMs) and cluster heads (CHs) choice. The projected CVoEG model divides VANET nodes (vehicles) into AN best variety of clusters (ONC) by exploitation Eigen gap heuristic. in an exceedingly given cluster, a vehicle are selected as a CH, if it's a most Eigen-centrality score. supported the CVoEG model, a reliable routing theme known as CEG-RAODV is projected to notice the foremost reliable journey (MRJ) from supply to destination. Our simulation results show that the projected theme considerably outperforms the present schemes in terms of responsibility, reliable routing request (RRR), packet delivery quantitative relation (PDR), finish to finish (E2E) delay.

Index Terms :- Evolving graph, VoEG model, Optimal number of clusters, cluster head, link reliability.

INTRODUCTION

Transport unintended networks (VANETs) aim to circularize safety data among vehicles to boost road safety and forestall accidents. VANETs square measure a special variety of mobile unintended networks (MANETs), wherever vehicles square measure equipped with a wireless communication facility (onboard unit (OBU)) to supply unintended property. it's many alternative flavors like vehicle-to-sensor, vehicle-to-vehicle, vehicle-to-Internet, and vehicle-to-road infrastructure. Communication is a vital analysis theme in VANETs. the first purpose of VANETs technology is to support safety and non-safety connected applications by mistreatment V2V and V2I among vehicles. VANETs have many challenges due to its dynamic nature. To cope with the dynamic structure of VANETs, an efficient and effective routing scheme is required for data dissemination. In the absence of an efficient routing vehicles may not be able to exchange information and will lose all the advantages offered by advanced VANETs technology. Many routing schemes have been proposed in the literature to tackle with the dynamic structure of VANET. The existing protocols are broadly divided into the following five subcategories: position-based protocols, route-discovery protocols,broad-casting protocols, infrastructure-based protocols, and cluster-based protocols. All these protocols

have limitations in their applicability and practical use. The broadcast-based protocols disseminate a large number of messages, which may cause high communication overhead in VANET. The route-discovery based protocols are not suitable for real-time scenarios, because of fixed route lifetime (instead of reliable route lifetime), fixed duration of route maintenance and long end-to-end delay. The position- based proto- cols use periodic messages to keep update its routing table for accurate information dissemination. The broadcast-based protocols also use the periodic messages approach. In a highly dynamic topology, the frequent periodic messages will cause communication overhead highly in both of the routing schemes as mentioned above. The infrastructure-based routing schemes are mostly area specific and cost-effective. The cluster-based protocols aim to scale back the amount of control messages by integrating vehicles into manage- able groups led by a superior vehicle called cluster head (CH). A cluster is made for intra-cluster data transmission (among cluster members (CMs)) also as for inter-clusters through roadside unit (RSU). In both cases, CH performs the responsibility of data transmission as well as cluster formation and CMs management. In intra-cluster, CH handles traffic control, media access, and QoS provision. While in case of wide VANETs, CH forms a dynamic virtual backbone to handle fundamental functions such as routing and channel allocation. The transferring of an ongoing vehicle data session from one RSU to another is called handover. The handover of fast-moving vehicles group is an open challenge. The performance will be worst if all the vehicles individually transfer their data session from a connected base station to another. Signalling overhead will be too much between the vehicle and RSU. The adaptation of clustering will significantly reduce the signalling overhead by converting many hand-overs to one (from CH to RSU). Ren et al. proposed a novel cluster-based routing scheme aim to form a stable group of vehicles leading by an optimal CH. The CH selection criterion was contention based on a back-off timer (calculated from relative speed/relative distance/link lifetime (LLT)). If the two vehicles have a very short gap between back-off times, then broadcast traverse time of cluster head announcement (CHA) will be higher than back-off time, which will not only produce broadcast storm but will also lead to cluster overlapping.

The proposed MOving ZOnes (MoZo) is the right approach to form optimal moving zones by measuring sim- ilarity scores. Apart from some environmental and predictions based specifications issues, MoZo also has a network disconnection issue due to pure V2V communications. Highly fragmented zones will not only increase the number of CHs but will also face network disconnection problem due to out of range zones.

The concept of an evolving graph is an emerging solution to tackle the randomized nature of VANETs. Eiza and Ni proposed VoEG (VANET oriented Evolving Graph) model for reliable and stable vehicular communication. The VoEG model is further extended to a new routing scheme called EG-RAODV (Evolving graph, Reliable Ad hoc on-Demand Distance Vector). The EG-RAODV reactively discovers Most Reliable Journey (MRJ) from source to destination by using Evolving Graph (EG) Dijkstra. Due to the evolving property, VoEG is an optimal choice to adopt in any dynamic vehicular networks. But the primary challenge to VoEG is the discovery of MRJ in highly denser topology. The EG-Dijkstra iteratively discovers all possible routes from source to destination and then selects MRJ from one of them. The authors considered sparse graph scenarios, where the frequent arrival of vehicles at a highway is not in practice. In moderate traffic, the computational complexity of EG-Dijkstra is O((|E|+|V|) logV) [22]. The performance of EG-Dijkstra in a flat structure network is profoundly affected due to underlying denser topological structure and excessive reliable route request (RRR) messages. The iterative discovery in a worst case does not only degrade computational performance but also affects space complexity badly. The RRR metric aims to measure the communication overhead in route discovery.

Clustering is an optimal solution to divide the network into manageable subparts to reduce the excessive overhead. Many supervised and unsupervised learning algorithms are available to classify network into groups in literature. Khan and Fan used conventional K-means to organize VANET into three clusters. The main issues with K-means are the pre-specified number of clusters, and secondly it may not classify vehicles, which are non-linearly separable in input space. In evolving VANETs, topology structure changes at every moment and the number of clusters may not be maintained. K-means is non-convex, which cant be optimized. Apart from machine learning classifications, many existing clustering approaches use different criteria for cluster formation and CH selection. The optimal number of clusters (ONC) is a challenging task in all existing clustering approaches. According to the literature more number of clusters tends to hand-off cost issue while fewer numbers cause frequent link disconnection. Clustering in an evolving- graph depends on connectivity of nodes at every moment. Hence its better to use a semi-convex approach based on data connectivity instead of geometrical proximity. In this work, spectral clustering is adopted during a heuristic approach to dealing with big challenge of ONC.

The primary purpose of this paper is to propose a novel cluster-based evolving graph model for VANETs, where the frequent arrival of vehicles with irregular intervals are in practice. The proposed VoEG model is extended to a cluster-

based VANETs oriented evolving graph (CVoEG) by using spectral clustering. In literature, different protocols use different selection criteria for cluster member selection such as ID, degree, propagation delay, velocity, travel time, average relative velocity, mean connection time, trust level, number of following vehicles, etc. The proposed CVoEG model in this paper uses link reliability as a selection criterion for CMs and CHs selection. A heuristic approach is adopted in CVoEG aims to find an optimal number of cluster (ONC) in an evolving VANET scenario. In this paper, cluster ranking is performed to measure the importance of each cluster member. In the CVoEG model, a vehicle having maximum eccentricity is selected as a CH. Finally, the CVoEG model is extended to CEG-RAODV routing scheme and analyzed in different traffic scenarios. The performance of CEG-RAODV is additionally analyzed on real traffic data of Inter-state 5 highway California. The significance of CEG-RAODV is evaluated by comparing its simulation results with that of EG-RAODV, R-TCRP (Reliable Tripple Cluster based Routing Protocol) (Extended version of TCRP) and RAODV. The aforementioned routing schemes are selected for performance comparison due to its close relationship with proposed CEG-RAODV routing scheme. Basically, CEG-RAODV is an extension of EG-RAODV scheme by adding unsupervised clustering (Eigen Decomposition using Spectral Clustering). Secondly, RAODV was considered in EG-RAODV as a base reference for com- paring its performance. Thats why here, RAODV is also considered to check the worth of our proposed clustering scheme. Lastly, R-TCRP is an unsupervised clustering scheme, which is more appropriate to compare with CEG-RAODV. TCRP was not directly comparable with CEG-RAODV because of different criteria for cluster formation and CHs selection. In this paper, TCRP is first extended to R-TCRP by using link reliability as a selection metric for cluster formation and CHs selection.

LITERATURE SURVEY

MoZo: A Moving Zone Based Routing Protocol Using Pure V2V Communication in VANETs Vehicular Ad-hoc Networks (VANETs) are an emerging field, whereby vehicle-to-vehicle communications can enable many new applications such as safety and entertainment services. Most VANET applications are enabled by different routing protocols. The design of such routing protocols, however, is quite challenging due to the dynamic nature of nodes (vehicles) in VANETs. To exploit the unique characteristics of VANET nodes, we design a moving-zone based architecture in which vehicles collaborate with one another to form dynamic moving zones so as to facilitate information dissemination. We propose a novel approach that introduces moving object modeling and indexing techniques from the theory of large moving object databases into the design of VANET routing protocols. The results of extensive simulation studies carried out on real road maps demonstrate the superiority of our approach compared with both clustering and non-clustering based routing protocols.

Connected Vehicles: Solutions and Challenges Providing various wireless connectivities for vehicles enables the communication between vehicles and their internal and

external environments. Such a connected vehicle solution is expected to be the next frontier for automotive revolution and the key to the evolution to next generation intelligent transportation systems (ITSs). Moreover, connected vehicles are also the building blocks of emerging Internet of Vehicles (IoV). Extensive research activities and numerous industrial initiatives have paved the way for the coming era of connected vehicles. In this paper, we focus on wireless technologies and potential challenges to provide vehicle-to- x connectivity. In particular, we discuss the challenges and review the state-of-the-art wireless solutions for vehicle-to- sensor, vehicle-to-vehicle, vehicle-to-Internet, and vehicle- to-road infrastructers connectivities. We also identify future research issues for building connected vehicles.

Independent zone routing: an adaptive hybrid routing framework for ad hoc wireless networks To effectively support communication in such a dynamic networking environment as the ad hoc networks, the routing framework has to be adaptable to the spatial and temporal changes in the characteristics of the network, such as traffic and mobility patterns. Multiscoping, as is provided through the concept of the Zone Routing Protocol (ZRP) for example, can serve as a basis for such an adaptive behaviour. The Zone Routing framework implements hybrid routing by every network node proactively maintaining routing information about its local neighbourhood called the routing zone, while reactively acquiring routes to destinations beyond the routing zone. In this paper, we propose the Independent Zone Routing (IZR) framework, an enhancement of the Zone Routing framework, which allows adaptive and distributed configuration for the optimal size of each node's routing zone, on the per-node basis. We demonstrate that the performance of IZR is significantly improved by its ability to automatically and dynamically tune the network routing operation, so as to flexibly and robustly support changes in the network characteristics and operational conditions. As a point of reference, through this form of adaptation, we show that the volume of routing control traffic overhead in the network can be reduced by an order of magnitude, under some set of parameter values. Furthermore, the adaptive nature of IZR enhance the scalability of these networks as well.

Geographic routing in city scenarios: Position-based routing, as it is used by protocols like Greedy Perimeter Stateless Routing (GPSR), is very well suited for highly dynamic environments such as inter-vehicle communication on highways. However, it has been discussed that radio obstacles, as they are found in urban areas, have a significant negative impact on the performance of position-based routing. In prior work we presented a position-based approach which alleviates this problem and is able to find robust routes within city environments. It is related to the idea of position-based source routing as proposed in for terminal-node routing. The algorithm needs global knowledge of the city topology as it is provided by a static street map. Given this information the sender determines the junctions that have to be traversed by the packet using the Dijkstra shortest path algorithm. Forwarding between junctions is then done in a position-based fashion. In this short paper we show how position-based routing can be

applied to a city scenario without assuming that nodes have access to a static street map and without using source routing.

Connectivity-Aware Routing (CAR) in Vehicular Ad-hoc Networks: Vehicular ad hoc networks using WLAN technology have recently received considerable attention. We present a position-based routing scheme called Connectivity-Aware Routing (CAR) designed specifically for inter-vehicle communication in a city and/o highway environment. A distinguishing property of CAR is the ability to not only locate positions of destinations but also to find connected paths between source and destination pairs. These paths are auto-adjusted on the fly, without a new discovery process. "Guards" help to track the current position of a destination, even if it travelled a substantial distance from its initially known location. For the evaluation of the CAR protocol we use realistic mobility traces obtained from a microscopic vehicular traffic simulator that is based on a model of driver behaviour and the real road maps of Switzerland.

UV-CAST: an urban vehicular broadcast protocol Several vehicular communication applications will involve multicast/broadcast communications where all vehicles in a certain region of interest are the intended recipients of particular messages. While there are several existing broadcast routing protocols for highway VANETs, very few solutions exist for urban VANETs in cities like New York City or Chicago. This article attempts to fill this gap by proposing a new broadcast routing protocol, Urban Vehicular Broadcast (UV-CAST), which addresses both the broadcast storm and disconnected network problems in urban VANETs. Key challenges imposed by urban VANETs as well as new mechanisms needed for meeting these challenges are identified and presented. Performance of the proposed UV-CAST protocol is evaluated in terms of network reachability, received distance, and network overhead in ideal Manhattan Street scenarios as well as in real cities, such as Pittsburgh. The overall performance of UV-CAST is excellent. DV-CAST: A distributed vehicular broadcast protocol for vehicular ad hoc networks The potential of infrastructure less vehicular ad hoc networks for providing safety and non-safety applications is quite significant. The topology of VANETs in urban, suburban, and rural areas can exhibit fully connected, fully disconnected, or sparsely connected behaviour, depending on the time of day or the market penetration rate of wireless communication devices. In this article we focus on highway scenarios, and present the design and implementation of a new distributed vehicular multi-hop broadcast protocol, that can operate in all traffic regimes, including extreme scenarios such as dense and sparse traffic regimes. DV- CAST is a distributed broadcast protocol that relies only on local topology information for handling broadcast messages in VANETs. It is shown that the performance of the proposed DV-CAST protocol in terms of reliability, efficiency, and scalability is excellent.

METHEDOLOGY AND DISCUSSION

The proposed cluster-based VANET oriented evolving graph (CVoEG) model is a novel approach to overcome the

demerits of the existing VoEG model. Since in the VoEG model, the performance of EG-Dijkstra degrades in the case of continual arrival of vehicles. The CVoEG model uses the same link reliability as that of the VoEG model. Due to the dynamicity of VANET, the structure of topology changes at every instant. Spectral clustering is an excellent classifier to cope with the instantaneous shape of VANET. Spectral clustering divides VoEG model into an optimal manageable number of groups, where each group having an appropriate clusterhead(CH).

Fig. 3. CVoEG model methodology.

CVoEG Model Methodology: In Figure 1, the complete methodology of the CVoEG model is shown. The first column represents the existing VoEG model approach whereas the rest of the two columns depict proposed CVoEG model.

Eigen decomposition, sometimes called spectral decom- position, involves the factoring of a matrix in terms of its eigenvalues and eigenvectors Eigen decomposition used for cost minimization in objects classification. In literature many existing machine learning algorithms are used for clustering (Partition based clustering i.e K-Means, K- Modes, K-Medoids, PAM, CLARA, CLARANS, PCM) in communication, but most of them are expected to yield poor results in term of clusters shapes (Non-convex), high dimensionality of data and size of data. Spectral clustering offers an attractive alternative approach, where clusters data use eigenvectors of a similarity/affinity matrix derived from the original dataset. In certain cases like fastevolving network, spectral clustering even becomes the only option. Eigen decomposition can be used in the reduction of dimensionality of the mobile vehicles.

REQUIREMENTS HARDWARE REQUIREMENTS

System: Pentium IV 2.4Ghz. Hard Disk: 40 GB.

Floppy Drive:1.44Mb. Monitor: 15VGA Colour. Mouse: Logitech.

RAM: 256 Mb.

SOFTWARE REQUIREMENTS

Operating System: Windows 7 Front End: JAVA or JSP Database: SQL SERVER 2008 Tools: Eclipse IDE

RESULT

The proposed CEG-RAODV has less E2E delay as compared to other schemes. The integration of CVoEG model has a terrific impact on timely packet delivery. The extreme variations in speeds do not affect the delivery time to the destination too much in CEG- RAODV. Since the network is divided into small manageable groups (clusters), hence the discovery boundary will be limited as compared to existed scheme.

CEG-RAODV is more stable as compared to EG- RAODV, R-TCRP, and RAODV in the context of throughput. The Proposed scheme shows outstanding performance with varying Ov . Since CVoEG model classifies vehicles into an optimal number of groups from reliability, hence the most reliable route will be

selected from source to destination. Due to the high reliability, the route will be robust to Ov and the average throughput will not be affected too much. The classifi- cation of vehicles based on link reliability improves mean route reliability and reduces control messages, which further reduces the computational cost. An increase in packet size has less effect on CEG-RAODVs PDR. Similarly, E2E delay and throughput are less affected as compared to existing schemes.

From all experiments, it is concluded that CVoEG model is an excellent addition to flat networks to improve its performance.

CONCLUSION

The classification of fast-evolving networks into manageable clusters is correct approach to boost the reliability of network. The proposed CVoEG model overcomes the deficiency of the present VoEG model by dividing the vehicular network into an optimal number of manageable groups. It significantly reduces the time complexity by eliminating unnecessary control messages. Scalability is that the main great thing about the proposed CVoEG model, where the optimal number of clusters (ONCs) are calculated in any vehicular topology. A fast- evolving VANET with high variations in speeds and inter- spacing is an appropriate scenario for the proposed CVoEG model. The performance of CVoEG won't be an excessive amount of good in static or less variant vehicular topology. the chosen CHs are more stable and reliable nodes because of the eigen-eccentricity score, but the choice process is kind of time-consuming. The proposed model easily extend able to a brand new reliable routing scheme called CEG RAODV by integrating the proposed CVoEG model and RAODV routing scheme.

REFERENCES

1. D. Lin, J. Kang, A. Squicciarini, Y. Wu, S. Gurung, and O. Tonguz, MoZo: A moving zone based routing protocol using pure V2V communication in VANETs, IEEE Trans. Mobile Comput., vol. 16, no. 5, pp. 13571370, May 2017.

2. N. Lu, N. Cheng, N. Zhang, X. Shen, and J. W. Mark, Connected vehicles: Solutions and challenges, IEEE Internet Things J., vol. 1, no. 4, pp. 289299, Aug. 2014.

3. P. Samar, M. R. Pearlman, and Z. J. Haas, Independent zone routing: An adaptive hybrid routing framework for spontaneous wireless networks, IEEE/ACM Trans. Netw., vol. 12, no. 4, pp. 595608, Aug. 2004.

4. C. Lochert, M. Mauve, H. Füßler, and H. Hartenstein, Geographic routing in city scenarios, ACM SIGMOBILE Mobile Comput. Commun. Rev., vol. 9, no. 1, pp. 6972, 2005.

5. V. Naumov and T. R. Gross, Connectivity-aware routing (CAR) in vehicular ad-hoc networks in Proc. 26th IEEE Int. Conf. Comput. Commun. (INFOCOM), May 2007, pp. 19191927.

6. W. Viriyasitavat, F. Bai, and O. K. Tonguz, UV-CAST: An urban vehicular broadcast protocol, in Proc. Veh. Netw. Conf., Dec. 2010, pp. 2532.

7. O. K. Tonguz N. Wisitpongphan and F.Bai, DV-

   CASTt:Adistributed

   vehicular broadcast protocol for vehicular spontanepous networks, IEEE Wireless Commun., vol. 17, no. 2, pp. 4757, Apr. 2010.

8. O.Tonguz, N. Wisitpongphan, F. Bait, P. Mudaliget, and V. Sadekart, Broadcasting in VANET, in Proc. Mobile Netw. Veh. Environ., May2007,pp. 712.

9. Y. Peng, Z. Abichar, and J. M. Chang, Roadside-aided routing (RAR) in vehicular networks, in Proc. IEEE Int. Conf. Commun., Jun. 2006,pp.36023607.

10. C. Shea, B. Hassanabadi, and S. Valaee, Mobility-based clustering in VANETs using affinity propagation, in Proc. GLOBECOM Global Telecommun. Conf., Nov./Dec. 2009, pp. 1 6.